# Decompositions of Circulant-Balanced Complete Multipartite Graphs Based on a Novel Labelling Approach

Authors: A. El-Mesady; Omar Bazighifan
Journal: Journal of Function Spaces
 (2022)

---

## Abstract

For applied scientists and engineers, graph theory is a strong and vital tool for evaluating and inventing solutions for a variety of issues. Graph theory is extremely important in complex systems, particularly in computer science. Many scientific areas use graph theory, including biological sciences, engineering, coding, and operational research. A strategy for the orthogonal labelling of a bipartite graphG with n edges has been proposed in the literature, yielding cyclic decompositions of balanced complete bipartite graphs Kn,n by the graph G. A generalization to circulant-balanced complete multipartite graphs Kn,n,⋯,n⏟m;m,n≥2, is our objective here. In this paper, we expand the orthogonal labelling approach used to generate cyclic decompositions for Kn,n to a generalized orthogonal labelling approach that may be used for decomposing Kn,n,⋯,n⏟m. We can decompose Kn,n,⋯,n⏟m into distinct graph classes based on the proposed generalized orthogonal labelling approach.


---

## Body

## 1. Introduction

As is well known, discrete mathematics is a field of mathematics that deals with countable processes and components. One of the most significant and intriguing disciplines in discrete mathematics is graph theory [1–3]. Graph theory is the study of structural models called graphs, which are made up of a collection of vertices and edges. Graph theory is extremely important in complex systems, particularly in computer science. Many scientific areas use graph theory, including engineering, coding [4, 5], operational research, biological sciences, and management sciences. For applied scientists and engineers, graph theory is a strong and vital science for evaluating and inventing solutions for a variety of issues. Graphs have recently been utilized as structural models for characterizing World Wide Web connections and the number of links necessary to move between web pages [6].Circulant graphs are a significant category of graphs [7–10]. Circulant graphs have gained a lot of attention in recent decades. The circulant graphs class includes complete graphs and classic rings topologies. The algebraic properties of circulant graphs have been studied in thousands of publications. Circulant graphs have been handled in a variety of graph applications, including wide area communication graphs, local area computer graphs, parallel processing architectures, very large-scale integrated circuit design, and distributed computing [11–13].Several traditional parallel and distributed systems were built on the foundation of circulant graphs [14–16]. Circulant graphs have a wide range of practical uses, such as a structure in chemical reaction models [17], multiprocessor cluster systems [18], small-world graph models [19], discrete cellular neural graphs [20], and as a basic structure for optical graphs [21], and so on.The study of circulant graphs, including their characterization, analysis, and applications, is currently a popular issue in research. Several papers have been published that deal with graph decompositions by simpler graphs [22–24]. Decompositions of circulant graphs have several excellent contributions. For Cayley graphs labelled with Abelian groups, the Hamilton decomposition was investigated in [25]. The circulant graph is a particular case of the Cayley graph. It has been demonstrated that two Hamilton cycles may be used to decompose four-regular connected Cayley graphs [26].For a certain recursive circulant graph, the Hamilton decompositions have been proven [27]. Every circulant graph has a corresponding circulant matrix [28]. Excellent descriptions of circulant matrices have been published in [28].Definition 1.
A circulant-balanced complete multipartite graphKn,n,⋯,n⏟m is a simple graph having mn=∑l=1mn vertices. The vertices of Kn,n,⋯,n⏟m are divided into m partitions of cardinality n; two vertices are said to be adjacent if they are found in two different partitions. The graph Kn,n,⋯,n⏟m has a degree equal to m−1n. The circulant graph Kn,n,⋯,n⏟m can be divided into δKn,n,δ=m2.Definition 2.
A caterpillar graphCab1,b2,⋯,ba is a tree formed by the path Pa=y1y2⋯ya by linking a vertex yi to bi new vertices where a≥1,b1,b2,⋯,ba are integers greater than zero, b1,ba≥1 and bi≥0 for i∈2,3,⋯,a−1.El-Mesady et al. have proposed an orthogonal labelling approach to decompose a certain circulant graph class with2n vertices and n degree [29]. Circulant-balanced complete bipartite graphs are the name for this type of graph which is denoted by Kn,n. In cognitive radio graphs and cloud computing, bipartite circulant graphs can address a variety of challenges. For a good survey on several decompositions of circulant graphs, see [30–34].In this study, we generalize the orthogonal labelling approach proposed in [29] to create edge decompositions of the graphs Kn,n,⋯,n⏟m;m,n≥2 which are considered a generalization to the graphs Kn,n. The following sections make up the current paper: The second section deals with the proposed novel orthogonal labelling approach. In the third section, the graph Kn,n,⋯,n⏟m is decomposed by infinite classes of graphs. We generate many decompositions of Kn,n,⋯,n⏟m by connected caterpillars in the fourth section. The fifth section introduces concluding remarks and future work.


## 2. A Novel Labelling Approach

Consider now the circulant-balanced complete multipartite graph with vertex setV=∪l=0m−1Vl, where V,l∈0,1,⋯,m−1 are m independent sets of vertices. There are bijective mappings φl:Vl⟶ℤn×l,l∈0,1,⋯,m−1 where the vertices in Vl are labelled by ℤn×l, see Figure 1.Figure 1
The labelling forKn,n,⋯,n⏟m.The distance between two verticesxi∈0i,1i,⋯,n−1i and yj∈0j,1j,⋯,n−1j,0≤i<j≤m−1 is the usual circular distance defined by dxi,yj=minxi−yj,n−xi−yj. The edge xi,yj is said to have length dxi,yj. Suppose G=V,E is a subgraph with mn vertices and m2n edges, a labelling
(1)ψk:VGki,j⟶ℤn×i,j,0≤i<j≤m−1,k=jifi=0,mi+jmodi+1ifi>0.is considered an orthogonal labelling ofG≅∪k=1wGki,j,w=m2,0≤i<j≤m−1 if,
(i)
Each graphGki,j has precisely two edges of length λ∈1,2,⋯,n−1/2, the length 0 is found once in Gki,j, and the length n/2 is found once in Gki,j if n is even(ii)
For everyλ∈1,2,⋯,n−1/2,G has precisely 2.m2=mm−1 edges of length λ,(iii)
The length 0 is foundm2 times in G,(iv)
The lengthn/2 is found m2 times in G if n is evenExample 1.
An orthogonal labelling ofK1,30,1∪P40,2∪K1,31,2 is shown in Figure 2.Definition 3.
SupposeG is a subgraph of Kn,n,⋯,n⏟m,x∈ℤn. Then G+x with EG+x=a+x,b+x:a,b∈EG is called the x-translate of G.Figure 2
An orthogonal labelling ofK1,30,1∪P40,2∪K1,31,2.The edge decomposition of circulant-balanced complete multipartite graphs and orthogonal labelling are linked in the next proposition.Proposition 4.
If and only if there is an orthogonal labelling ofG≅∪k=1wGki,j,0≤i<j≤m−1, an edge decomposition of Kn,n,⋯,n⏟m can be constructed by G.Proof.
Our goal is to show thatEGi,j+ω∩EGi,j+σ=ϕ for all ω,σ∈ℤn. We assume, by way of contradiction, that EGi,j+ω∩EGi,j+σ∣≥1 for ω,σ∈ℤn with ω≠σ. For the lengths λ∈1,2,⋯,n−1/2, which are repeated twice in Gi,j, let a,b and c,d be two edges of EGi,j+ω∩EGi,j+σ with length λ, then a−ω,b−ω,c−ω,d−ω and a−σ,b−σ,c−σ,d−σ are various edges with length λ in EGi,j. However, this is a contradiction because Gi,j verifies the orthogonal labelling requirement (i). Let a,b belong to EGi,j+ω∩EGi,j+σ with length l∈0,n/2,n is even, then a−ω,b−ω and a−σ,b−σ are distinct edges in EGi,j, both with length l. However, this is a contradiction because Gi,j verifies the orthogonal labelling requirement (i). Hence, ∩x∈ℤnEG+x=φ. Also, for every λ∈1,2,⋯,n−1/2,G has precisely 2.m2=mm−1 edges with length λ, the length 0 is only found m2 times in G, the length n/2 is only found m2 times in G if n is even. Consequently,
(2)∪x∈ℤnEG+x=EKn,n,⋯,n⏟m.Example 2.
An example of edge decomposition ofK3,3,3 by K1,30,1∪P40,2∪K1,31,2 is shown in Figure 3.Figure 3
An edge decomposition ofK3,3,3 by K1,30,1∪P40,2∪K1,31,2.In what follows, based on the aforementioned orthogonal labelling approach, we will decompose the circulant-balanced complete multipartite graphKn,n,⋯,n⏟m by the G≅∪k=1wGki,j, where the graphs Gki,j,k∈1,2,⋯,w,w=m2,i≠j∈0,1,⋯,m−1 are isomorphic. Also, we will consider
(3)k=jifi=0,im+jmodi+1ifi>0.


## 3. Decompositions ofKn,n,⋯,n⏟m by Several Classes of Graphs

Theorem 5.
Letn≥5,m≥2 be integers. Then, there is an orthogonal labelling for G1≅∪0≤i<j≤m−1K2,2∪K1,n−4i,j.Proof.
SupposeVK2,2∪K1,n−4i,j=vs:s∈0,1,2,⋯,n. The mapping ψk can be used to define an orthogonal labelling for the subgraph G1, which can be defined by ψk:VK2,2∪K1,n−4i,j⟶ℤn×i,j which is defined by ψkv0=n+3/2i,ψkv1=n−1/2i,ψkv2=n+1/2i,ψkvs+3=n−1/2+sj,s∈0,⋯,n−5, and the edge set of K2,2∪K1,n−4i,j is
(4)EK2,2∪K1,n−4i,j=n+32i,nj,n+32i,n+1j,n−12i,nj,n−12i,n+1j,n+12i,n−12j∪n+12i,n+12+sj:s∈0,1,⋯,n−6,
see Figure4. From the edge set of G1, the following conditions are verified: Each graph K2,2∪K1,n−4i,j has precisely two edges of length λ∈1,2,⋯,n−1/2, the length 0 is found once in K2,2∪K1,n−4i,j, the length n/2 is found once in K2,2∪K1,n−4i,j if n is even, for every λ∈1,2,⋯,n−1/2,G1 has precisely 2.m2=mm−1 edges of length λ, the length 0 is found m2 times in G1, and the length n/2 is found m2 times in G1 if n is even. Hence, Kn,n,⋯,n⏟m can be decomposed by G1.Theorem 6.
Letn>1,m≥2 be integers. Then, there is an orthogonal labelling for G2≅∪0≤i<j≤m−1K2,ni,j.Proof.
SupposeVK2,ni,j is VK2,ni,j=vs:s∈0,1,2,⋯,n+1. The mapping ψk can be used to define an orthogonal labelling for the subgraph G2, which can be defined by ψk:VK2,ni,j⟶ℤ2n×i,j which is defined by
(5)ψkvs=si,s∈0,1,ψkvs+2=2s−1mod2nj,s∈1,⋯,n,and the edge set of K2,ni,j is
(6)EK2,ni,j=0i,2sj:s∈0,1,⋯,n−1∪1i,2smod2nj:s∈1,⋯,n,
see Figure5. From the edge set of G2, the following conditions are verified: Each graph K2,ni,j has precisely two edges of length λ∈1,2,⋯,2n−1/2, the length 0 is found once in K2,ni,j, the length n is found once in K2,ni,j, for every λ∈1,2,⋯,2n−1/2,G2 has precisely 2.m2=mm−1 edges of length λ, the length 0 is found m2 times in G2, and the length n is found m2 times in G2. Hence, K2n,2n,⋯,2n⏟m can be decomposed by G2.Theorem 7.
Letn≡2mod6 or n≡4mod6,m≥2. Then, there is an orthogonal labelling for
(7)G3≅∪0≤i<j≤m−1n2K1,2i,j.Proof.
SupposeVn/2K1,2i,j=vs:s∈0,1,2,⋯,2n−1. The mapping ψk can be used to define an orthogonal labelling for the subgraph G3, which can be defined by ψk:Vn/2K1,2i,j⟶ℤn×i,j which is defined by ψkvs=si,s∈0,1,⋯,n−1,ψkvn+s=2smodnj,s∈0,1,⋯,n−1, and the edge set of n/2K1,2i,j is En/2K1,2i,j=si,2smodnj:s∈0,1,2,⋯,n−1, see Figure 6. From the edge set of G3, the following conditions are verified: Each graph n/2K1,2i,j has precisely two edges of length λ∈1,2,⋯,n−1/2, the length 0 is found once in n/2K1,2i,j, the length n/2 is found once in n/2K1,2i,j, for every λ∈1,2,⋯,n−1/2,G3 has precisely 2.m2=mm−1 edges of length λ, the length 0 is found m2 times in G3, and the length n/2 is found m2 times in G3. Hence, Kn,n,⋯,n⏟m can be decomposed by G3.Theorem 8.
Letn≥9,m≥2 be integers. Then, there is an orthogonal labelling for
(8)G4≅∪0≤i<j≤m−1C8∪K1,n−8i,j.Proof.
SupposeVC8∪K1,n−8i,j=vs:s∈0,1,2,⋯,n. The mapping ψk can be used to define an orthogonal labelling for the subgraph G4, which can be defined by ψk:VC8∪K1,n−8i,j⟶ℤn×i,j which is defined by
(9)ψkv0=00,ψkv1=10,ψkv2=20,ψkv3=40,ψkv4=80,ψkvs=s−41,s∈5,⋯,n,and the edge set of C8∪K1,n−8i,j is
(10)EC8∪K1,n−8i,j=0i,2j,0i,4j,4i,2j,4i,3j,2i,3j,2i,5j,8i,4j,8i,5j,1i,1j
∪1i,sj:s∈6,7,⋯,n−4, see Figure 7. From the edge set of G4, the following conditions are verified: Each graph C8∪K1,n−8i,j has precisely two edges of length λ∈1,2,⋯,n−1/2, the length 0 is found once in C8∪K1,n−8i,j, the length n/2 is found once in C8∪K1,n−8i,j if n is even, for every λ∈1,2,⋯,n−1/2,G4 has precisely 2.m2=mm−1 edges of length λ, the length 0 is found m2 times in G4, and the length n/2 is found m2 times in G4 if n is even. Hence, Kn,n,⋯,n⏟m can be decomposed by G4.Theorem 9.
Letn≥7,m≥2 be integers. Then, there is an orthogonal labelling for G5≅∪0≤i<j≤m−1C6∪K1,1∪K1,n−7i,j..Proof.
SupposeVK1,1∪C6∪K1,n−7i,j=vs:s∈0,1,2,⋯,n. The mapping ψk can be used to define an orthogonal labelling for the subgraph G5, which can be defined by ψk:VK1,1∪C6∪K1,n−7⟶ℤn×i,j which is defined by
(11)ψkv0=0i,ψkv1=1i,ψkv2=3i,ψkv3=4i,ψkv4=6i,ψkv5=1j,ψkv6=2j,ψkv7=3j,
ψkv8=5j,ψkvs=s−2j,s∈9,⋯,n+1, and the edge set of K1,1∪C6∪K1,n−7i,j is
(12)EK1,1∪C6∪K1,n−7i,j=1i,1j,0i,2j,0i,3j,4i,2j,4i,5j,6i,3j,6i,5j∪3i,sj:s∈7,⋯,n−1,
see Figure8. From the edge set of G5, the following conditions are verified: Each graph K1,1∪C6∪K1,n−7i,j has precisely two edges of length λ∈1,2,⋯,n−1/2, the length 0 is found once in K1,1∪C6∪K1,n−7i,j, the length n/2 is found once in K1,1∪C6∪K1,n−7i,j if n is even, for every λ∈1,2,⋯,n−1/2,G5 has precisely 2.m2=mm−1 edges of length λ, the length 0 is found m2 times in G5, and the length n/2 is found m2 times in G5 if n is even. Hence, Kn,n,⋯,n⏟m can be decomposed by G5.Theorem 10.
Letn≥5,m≥2 be integers. Then, there is an orthogonal labelling for G6≅∪0≤i<j≤m−12K2∪K1,n−2i,j.Proof.
SupposeV2K1,1∪K1,n−2i,j=vs:s∈0,1,2,⋯,n+2. The mapping ψk can be used to define an orthogonal labelling for the subgraph G6, which can be defined by ψk:V2K1,1∪K1,n−2i,j⟶ℤn×i,j which is defined by
(13)ψkv0=0i,ψkv1=1i,ψkv2=n−1i,ψkvs+3=sj,s∈0,⋯,n−1,
and the edge set of2K1,1∪K1,n−2i,j is
(14)E2K1,1∪K1,n−2i,j=0i,sj:s∈0,1,⋯,n−3∪1i,n−1j,n−1i,n−2j,
see Figure9. From the edge set of G6, the following conditions are verified: Each graph 2K1,1∪K1,n−2i,j has precisely two edges of length λ∈1,2,⋯,n−1/2, the length 0 is found once in 2K1,1∪K1,n−2i,j, the length n/2 is found once in 2K1,1∪K1,n−2i,j if n is even, for every λ∈1,2,⋯,n−1/2,G6 has precisely 2.m2=mm−1 edges of length λ, the length 0 is found m2 times in G6, and the length n/2 is found m2 times in G6 if n is even. Hence, Kn,n,⋯,n⏟m can be decomposed by G6.Theorem 11.
Letn>1,m≥2 be integers. Then, there is an orthogonal labelling for G7≅∪0≤i<j≤m−1Pn+1i,j.Proof.
SupposeVPn+1i,j=vs:s∈0,1,2,⋯,n. The mapping ψk can be used to define an orthogonal labelling for the subgraph G7, which can be defined by ψk:VPn+1i,j⟶ℤn×i,j which is defined by
(15)ψkvs=n−smodni,s∈0,1,⋯,n−32,ψkvn−1/2=n+12i,ψkvn−3/2+s+2=sj,
s∈0,1,⋯,n−1/2, and the edge set of Pn+1i,j is EPn+1i,j=n+1/2i,n−1/2j∪.n−smodni,s+αj:s∈0,1,⋯,n−3/2,α∈0,1,see Figure 10. From the edge set of G7, the following conditions are verified: Each graph Pn+1i,j has precisely two edges of length λ∈1,2,⋯,n−1/2, the length 0 is only present once in Pn+1i,j, the length n/2 is found once in Pn+1i,j if n is even, for every λ∈1,2,⋯,n−1/2,G7 has precisely 2.m2=mm−1 edges of length λ, the length 0 is found m2 times in G7, and the length n/2 is found m2 times in G7 if n is even. Hence, Kn,n,⋯,n⏟m can be decomposed by G7.Theorem 12.
Letn≡1mod6,n≡5mod6,m≥2 be an integer. Then, there is an orthogonal labelling for Kn,n,⋯,n⏟m by G8≅∪0≤i<j≤m−1nK1,1i,j.Proof.
SupposeVnK1,1i,j is VnK1,1i,j=vs:s∈0,1,2,⋯,2n−1. The mapping ψk can be used to define an orthogonal labelling for the subgraph G8, which can be defined by ψk:VnK1,1i,j⟶ℤn×i,j which is defined by ψkvs=si,s∈0,1,⋯,n−1,ψkvn+s−1=2s−1modnj,s∈1,2,⋯,n, and the edge set of nK1,1i,j is EnK1,1i,j=si,2smodnj:s∈0,1,⋯,n−1, see Figure 11. From the edge set of G8, the following conditions are verified: Each graph nK1,1i,j has precisely two edges of length λ∈1,2,⋯,n−1/2, the length 0 is found once in nK1,1i,j, the length n/2 is found once in nK1,1i,j if n is even, for every λ∈1,2,⋯,n−1/2,G8 has precisely 2.m2=mm−1 edges of length λ, the length 0 is found m2 times in G8, and the length n/2 is found m2 times in G8 if n is even. Hence, Kn,n,⋯,n⏟m can be decomposed by G8.Theorem 13.
Letn≥1,m≥2 be integers. Then, there is an orthogonal labelling for
(16)G9≅∪0≤i<j≤m−1K1,2∪K2,2ni,j.Proof.
SupposeVK1,2∪K2,2ni,j=vs:s∈0,1,2,⋯,2n+4. The mapping ψk can be used to define an orthogonal labelling for the subgraph G9, which can be defined by ψk:VK1,2∪K2,2ni,j⟶ℤ4n+2×i,j which is defined by
(17)ψkv0=4n+1i,ψkv1=2ni,ψkv2=0i,ψkv3=2n+1i,ψkv4=4n+1j,
ψkvs=n+s−4j,s∈5,⋯,n+4,ψkvn+s=2n+s−3j,s∈5,⋯,n+4, and the edge set of K1,2∪K2,2ni,j is
(18)EK1,2∪K2,2ni,j=4n+1i,4n+1j,2ni,4n+1j∪0i,sj,2n+1i,sj:s∈n+1,⋯,2n∪0i,sj,2n+1i,sj,s∈2n+2,⋯,3n+1,
see Figure12. From the edge set of G9, the following conditions are verified: Each graph K1,2∪K2,2ni,j has precisely two edges of length λ∈1,2,⋯,4n+1/2, the length 0 is found once in K1,2∪K2,2ni,j, the length 2n+1 is found once in K1,2∪K2,2ni,j, for every λ∈1,2,⋯,4n+1/2,G9 has precisely 2.m2=mm−1 edges of length λ, the length 0 is found m2 times in G9, and the length 2n+1 is found m2 times in G9. Hence, K4n+2,4n+2,⋯,4n+2⏟m can be decomposed by G9.Theorem 14.
Letn≥2,m≥2 be integers. Then, there is an orthogonal labelling for
(19)G10≅∪0≤i<j≤m−12K1,ni,j.Proof.
SupposeV2K1,ni,j=vs:s∈0,1,2,⋯,2n+1. The mapping ψk can be used to define an orthogonal labelling for the subgraph G10, which can be defined by ψk:V2K1,ni,j⟶ℤ2n×i,j which is defined by ψkv0=n−2i,ψkv1=ni,ψkvs+2=sj,s∈0,⋯,2n−1, and the edge set of 2K1,ni,j is E2K1,ni,j=ni,2s+1j,n−2i,2sj:s∈0,1,⋯,n−1, see Figure 13. From the edge set of G10, the following conditions are verified: Each graph 2K1,ni,j has precisely two edges of length λ∈1,2,⋯,2n−1/2, the length 0 is found once in 2K1,ni,j, the length n is found once in 2K1,ni,j, for every λ∈1,2,⋯,2n−1/2,G10 has precisely 2.m2=mm−1 edges of length λ, the length n is found m2 times in G10, and the length 0 is found m2 times in G10. Hence, K2n,2n,⋯,2n⏟m can be decomposed by G10.Theorem 15.
For all positive integersn with gcd n,3=1,m≥2. Then, there is an orthogonal labelling for
(20)G11≅∪0≤i<j≤m−1nK2,2i,j.Proof.
SupposeVnK2,2i,j is VnK2,2i,j=vs:s∈0,1,2,⋯,4n−1. The mapping ψk can be used to define an orthogonal labelling for the subgraph G11, which can be defined by ψk:VnK2,2i,j⟶ℤ4n×i,j which is defined by
(21)ψkvs=si,s∈0,1,⋯,2n−1,ψkv2n+s=2smod4nj,s∈0,1,⋯,2n−1,
and the edge set ofnK2,2i,j is
(22)EnK2,2i,j=si,2sj:s∈0,1,⋯,2n−1∪s−2ni,2s−2nmod4nj:s∈2n,⋯,4n−1.
From the edge set ofG11, the following conditions are verified: Each graph nK2,2i,j has precisely two edges of length λ∈1,2,⋯,4n−1/2, the length 0 is found once in nK2,2i,j, the length 2n is found once in nK2,2i,j, for every λ∈1,2,⋯,4n−1/2,G11 has precisely 2.m2=mm−1 edges of length λ, the length 0 is found m2 times in G11, and the length 2n is found m2 times in G11. Hence, K4n,4n,⋯,4n⏟m can be decomposed by G11.Theorem 16.
Letn≥3,m≥2 be integers. Then, there is an orthogonal labelling for
(23)G12≅∪0≤i<j≤m−1K3,ni,j.Proof.
SupposeVK3,ni,j=vs:s∈0,1,2,⋯,2n+4. The mapping ψk can be used to define an orthogonal labelling for the subgraph G12, which can be defined by ψk:VK3,ni,j⟶ℤ3n×i,j which is defined by ψkv0=0i,ψkv1=2i,ψkv2=4i,ψkvs=3s−3j,s∈3,⋯,n+2, and the edge set of K3,ni,j is EK3,ni,j=ai,bj:a∈0,2,4,b∈0,3,6,⋯,3n−3, see Figure 14. From the edge set of G12, the following conditions are verified: Each graph K3,ni,j has precisely two edges of length λ∈1,2,⋯,3n−1/2, the length 0 is only present once in K3,ni,j, the length 3n/2 is found once in K3,ni,j if n is even, for every λ∈1,2,⋯,3n−1/2,G12 has precisely 2.m2=mm−1 edges of length λ, the length 0 is found m2 times in G12, and the length 3n/2 is found m2 times in G12 if n is even. Hence, K3n,3n,⋯,3n⏟m can be decomposed by G12.Theorem 17.
Letn≥4,m≥2 be integers. Then, there is an orthogonal labelling for
(24)G13≅∪0≤i<j≤m−1K1,1∪K1,2∪K1,4∪K1,2n−6i,j.Proof.
SupposeVK1,1∪K1,2∪K1,4∪K1,2n‐6i,j=vs:s∈0,1,2,⋯,2n+4. The mapping ψk can be used to define an orthogonal labelling for the subgraph G13, which can be defined by ψk:VK1,1∪K1,2∪K1,4∪K1,2n‐6i,j⟶ℤ2n+1×i,j which is defined by
(25)ψkv0=3i,ψkv1=2n−3i,ψkv2=2i,ψkv3=0i,ψkv4=2ni,ψkv5=3j,ψkv6=2nj,ψkv7=0j,ψkv8=1j,ψkv9=2n−2j,ψkv10=2n−1j,ψkvs+1=s−6j,s∈10,⋯,2n+3,
and the edge set ofK1,1∪K1,2∪K1,4∪K1,2n‐6i,j is
(26)EK1,1∪K1,2∪K1,4∪K1,2n‐6i,j=3i,3j,2n−3i,2nj,2i,2nj,2ni,0j,2ni,1j,2ni,2n−2j,2ni,2n−1j∪0i,aj:a∈4,5,⋯,2n−3,
see Figure15. From the edge set of G13, the following conditions are verified: Each graph K1,1∪K1,2∪K1,4∪K1,2n‐6i,j has precisely two edges of length λ∈1,2,⋯,n, the length 0 is found once in K1,1∪K1,2∪K1,4∪K1,2n‐6i,j, for every λ∈1,2,⋯,n,G13 has precisely 2.m2=mm−1 edges of length λ, and the length 0 is found m2 times in G13. Hence, K2n+1n,2n+1n,⋯,2n+1n⏟m can be decomposed by G13.Figure 4
The labelling forK2,2∪K1,n−4i,j.Figure 5
The labelling forK2,ni,j.Figure 6
The labelling forn/2K1,2i,j.Figure 7
The labelling forC8∪K1,n−8i,j.Figure 8
The labelling forK1,1∪C6∪K1,n−7i,j.Figure 9
The labelling for2K1,1∪K1,n−2i,j.Figure 10
The labelling forPn+1i,j.Figure 11
The labelling fornK1,1i,j.Figure 12
The labelling forK1,2∪K2,2ni,j.Figure 13
The labelling for2K1,ni,j.Figure 14
The labelling forK3,ni,j.Figure 15
The labelling forK1,1∪K1,2∪K1,4∪K1,2n‐6i,j.


## 4. Decompositions ofKn,n,⋯,n⏟m by Connected Caterpillars

Theorem 18.
Letn≥2,m≥2 be integers. Then, there is an orthogonal labelling for
(27)G14≅∪0≤i<j≤m−1C21,n−2i,j,Proof.
SupposeVC21,n−2i,j=vs:s∈0,1,⋯,n. The mapping ψk can be used to define an orthogonal labelling for the subgraph G14, which can be defined by ψk:VC21,n−2i,j⟶ℤn×i,j which is defined by
(28)ψkv0=0i,ψkv1=1i,ψkv2=0j,ψkvs=s−1j,s∈3,4,⋯,n,
and the edge set ofC21,n−2i,j is
(29)EC21,n−2i,j=0i,0j,1i,0j∪1i,sj:s∈2,3,⋯,n−1,
see Figure16. From the edge set of G14, the following conditions are verified: Each graph C21,n−2i,j has precisely two edges of length λ∈1,2,⋯,n−1/2, the length 0 is found once in C21,n−2i,j, the length n/2 is found once in C21,n−2i,j, for every λ∈1,2,⋯,n−1/2,G14 has precisely 2.m2=mm−1 edges of length λ, the length n/2 is found m2 times in G14, and the length 0 is found m2 times in G14. Hence, Kn,n,⋯,n⏟m can be decomposed by G14.Theorem 19.
Letn≥3,m≥2 be integers. Then, there is an orthogonal labelling for
(30)G15≅∪0≤i<j≤m−1C31,0,n−3i,j.Proof.
SupposeVC31,0,n−3i,j=vs:s∈0,1,⋯,n. The mapping ψk can be used to define an orthogonal labelling for the subgraph G15, which can be defined by ψk:VC31,0,n−3i,j⟶ℤn×i,j which is defined by ψkv0=0i,ψkv1=n−1i,ψkv2=0j,ψkv3=1j,ψkvs=s−1j,s∈4,5,⋯,n, and the edge set of C31,0,n−3i,j is
(31)EC31,0,n−3i,j=0i,0j,n−1i,0j,n−1i,1j∪0i,sj:s∈3,4,⋯,n−1,
see Figure17. From the edge set of G15, the following conditions are verified: Each graph C31,0,n−3i,j has precisely two edges of length λ∈1,2,⋯,n−1/2, the length 0 is found once in C31,0,n−3i,j, the length n/2 is found once in C31,0,n−3i,j if n is even, for every λ∈1,2,⋯,n−1/2,G15 has precisely 2.m2=mm−1 edges of length λ, the length n/2 is found m2 times in G15 if n is even, and the length 0 is found m2 times in G15. Hence, Kn,n,⋯,n⏟m can be decomposed by G15.Theorem 20.
Letn≥4,m≥2 be integers. Then, there is an orthogonal labelling for
(32)G16≅∪0≤i<j≤m−1C41,0,0,n−4i,j.Proof.
SupposeVC41,0,0,n−4i,j=vs:s∈0,1,⋯,n. The mapping ψk can be used to define an orthogonal labelling for the subgraph G16, which can be defined by ψk:VC41,0,0,n−4i,j⟶ℤn×i,j which is defined by
(33)ψkv0=0i,ψkv1=n−1i,ψkv2=0j,ψkv3=1j,ψkv4=n−2j,ψkvs+3=sj,
s∈2,3,⋯,n−3, and the edge set of C41,0,0,n−4i,j is
(34)EC41,0,0,n−4i,j=0i,0j,0i,1j,n−1i,n−2j,n−1i,1j∪si,0j:s∈2,3,⋯,n−3,
see Figure18. From the edge set of G16, the following conditions are verified: Each graph C41,0,0,n−4i,j has precisely two edges of length λ∈1,2,⋯,n−1/2, the length 0 is found once in C41,0,0,n−4i,j, the length n/2 is found once in C41,0,0,n−4i,j if n is even, for every λ∈1,2,⋯,n−1/2,G16 has precisely 2.m2=mm−1 edges of length λ, the length n/2 is found m2 times in G16 if n is even, and the length 0 is found m2 times in G16. Hence, Kn,n,⋯,n⏟m can be decomposed by G16.Theorem 21.
Letn≥5,m≥2 be integers. Then, there is an orthogonal labelling for
(35)G17≅∪0≤i<j≤m−1C51,0,0,0,n−5i,j.Proof.
SupposeVC51,0,0,0,n−5i,j=vs:s∈0,1,⋯,n. The mapping ψk can be used to define an orthogonal labelling for the subgraph G17, which can be defined by ψk:VC51,0,0,0,n−5i,j⟶ℤn×i,j which is defined by
(36)ψkv0=0j,ψkv1=0i,ψkv2=2j,ψkv3=4i,ψkv4=3j,ψkv5=2i,ψkvs+1=sj,s∈5,6,⋯,n−1,
and the edge set ofC51,0,0,0,n−5i,j is
(37)EC51,0,0,0,n−5i,j=0i,0j,2i,3j,0i,2j,4i,2j,4i,3j∪2i,sj:s∈5,6,⋯,n−1,
see Figure19. From the edge set of G17, the following conditions are verified: Each graph C51,0,0,0,n−5i,j has precisely two edges of length λ∈1,2,⋯,n−1/2, the length 0 is found once in C51,0,0,0,n−5i,j, the length n/2 is found once in C51,0,0,0,n−5i,j if n is even, for every λ∈1,2,⋯,n−1/2,G17 has precisely 2.m2=mm−1 edges of length λ, the length n/2 is found m2 times in G17 if n is even, and the length 0 is found m2 times in G17. Hence, Kn,n,⋯,n⏟m can be decomposed by G17.Theorem 22.
Letn≥6,m≥2 be integers. Then, there is an orthogonal labelling for
(38)G18≅∪0≤i<j≤m−1C61,0,0,0,0,n−6i,j.Proof.
SupposeVC61,0,0,0,0,n−6i,j=vs:s∈0,1,⋯,n. The mapping ψk can be used to define an orthogonal labelling for the subgraph G18, which can be defined by ψk:VC61,0,0,0,0,n−6i,j⟶ℤn×i,j which is defined by
(39)ψkv0=0j,ψkv1=n−1i,ψkv2=n−2j,ψkv3=0i,ψkv4=2j,ψkv5=2i,.
ψkv6=n−1j,ψkvs+4=si,s∈3,4,⋯,n−4, and the edge set of C61,0,0,0,0,n−6i,j is
(40)EC61,0,0,0,0,n−6i,j=n−1i,0j,n−1i,n−2j,0i,n−2j,0i,2j,2i,2j,2i,n−1j∪si,n−1j:s∈3,4,⋯,n−4,
see Figure20. From the edge set of G18, the following conditions are verified: Each graph C61,0,0,0,0,n−6i,j has precisely two edges of length λ∈1,2,⋯,n−1/2, the length 0 is only present once in C61,0,0,0,0,n−6i,j, the length n/2 is found once in C61,0,0,0,0,n−6i,j if n is even, for every λ∈1,2,⋯,n−1/2,G18 has precisely 2.m2=mm−1 edges of length λ, the length n/2 is found m2 times in G18 if n is even, and the length 0 is found m2 times in G18. Hence, Kn,n,⋯,n⏟m can be decomposed by G18.Theorem 23.
Letn≥7,m≥2 be integers. Then, there is an orthogonal labelling for
(41)G19≅∪0≤i<j≤m−1C71,0,0,0,0,0,n−7i,j.Proof.
SupposeVC71,0,0,0,0,0,n−7i,j=vs:s∈0,1,⋯,n. The mapping ψk can be used to define an orthogonal labelling for the subgraph G19, which can be defined by ψk:VC71,0,0,0,0,0,n−7i,j⟶ℤn×i,j which is defined by ψkv0=2j,ψkv1=1i,ψkv2=0j,ψkv3=0i,ψkv4=3j,ψkv5=6i,ψkv6=4j,ψkv7=2i,ψkvs+2=sj,s∈6,7,⋯,n−2, and the edge set of C71,0,0,0,0,0,n−7i,j is
(42)EC71,0,0,0,0,0,n−7i,j=1i,2j,1i,0j,0i,0j,0i,3j,6i,3j,6i,4j,2i,4j∪2i,sj:s∈6,7,⋯,n−2,see Figure 21. From the edge set of G19, the following conditions are verified: Each graph C71,0,0,0,0,0,n−7i,j has precisely two edges of length λ∈1,2,⋯,n−1/2, the length 0 is only present once in C71,0,0,0,0,0,n−7i,j, the length n/2 is found once in C71,0,0,0,0,0,n−7i,j if n is even, for every λ∈1,2,⋯,n−1/2,G19 has precisely 2.m2=mm−1 edges of length λ, the length n/2 is found m2 times in G19 if n is even, and the length 0 is found m2 times in G19. Hence, Kn,n,⋯,n⏟m can be decomposed by G19.Theorem 24.
Letn≥8,m≥2 be integers. Then, there is an orthogonal labelling for
(43)G20≅∪0≤i<j≤m−1C81,0,0,0,0,0,0,n−8i,j.Proof.
SupposeVC81,0,0,0,0,0,0,n−8i,j=vs:s∈0,1,⋯,n. The mapping ψk can be used to define an orthogonal labelling for the subgraph G20, which can be defined by ψk:VC81,0,0,0,0,0,0,n−8i,j⟶ℤn×i,j which is defined byψkv0=6i,ψkv1=5j,ψkv2=4i,ψkv3=2j,ψkv4=0i,ψkv5=0j,ψkv6=3i,ψkv7=6j,.
ψkv8=2i,φvi+2=i1,i∈7,8,⋯,n−2, and the edge set of C81,0,0,0,0,0,0,n−8i,j is
(44)EC81,0,0,0,0,0,0,n−8i,j=6i,5j,4i,2j,0i,2j,0i,0j,3i,0j,3i,61,2i,6j∪2i,sj:s∈7,8,⋯,n−2,
see Figure22. From the edge set of G20, the following conditions are verified: Each graph C81,0,0,0,0,0,0,n−8i,j has precisely two edges of length λ∈1,2,⋯,n−1/2, the length 0 is found once in C81,0,0,0,0,0,0,n−8i,j, the length n/2 is found once in C81,0,0,0,0,0,0,n−8i,j if n is even, for every λ∈1,2,⋯,n−1/2,G20 has precisely 2.m2=mm−1 edges of length λ, the length n/2 is found m2 times in G20 if n is even, and the length 0 is found m2 times in G20. Hence, Kn,n,⋯,n⏟m can be decomposed by G20.Theorem 25.
Letn≥9,m≥2 be integers. Then, there is an orthogonal labelling for
(45)G21≅∪0≤i<j≤m−1C91,0,0,0,0,0,0,0,n−9i,j.Proof.
SupposeVC91,0,0,0,0,0,0,0,n−9i,j=vs:s∈0,1,⋯,n. The mapping ψk can be used to define an orthogonal labelling for the subgraph G21, which can be defined by ψk:VC91,0,0,0,0,0,0,0,n−9i,j⟶ℤn×i,j which is defined byψkv0=6j,ψkv1=4i,ψkv2=2j,ψkv3=1i,ψkv4=0j,ψkv5=0i,ψkv6=4j,ψkv7=8i,.
ψkv8=5j,ψkv9=2i,ψkvs+3=sj,s∈7,8,⋯,n−3, and the edge set of C91,0,0,0,0,0,0,0,n−9i,j is
(46)EC91,0,0,0,0,0,0,0,n−9i,j=4i,6j,4i,2j,1i,2j,1i,0j,0i,0j,0i,4j,8i,4j,8i,5j,2i,5j∪2i,sj:s∈7,8,⋯,n−3,
see Figure23. From the edge set of G21, the following conditions are verified: Each graph C91,0,0,0,0,0,0,0,n−9i,j has precisely two edges of length λ∈1,2,⋯,n−1/2, the length 0 is found once in C91,0,0,0,0,0,0,0,n−9i,j, the length n/2 is found once in C91,0,0,0,0,0,0,0,n−9i,j if n is even, for every λ∈1,2,⋯,n−1/2,G21 has precisely 2.m2=mm−1 edges of length λ, the length n/2 is found m2 times in G21 if n is even, and the length 0 is found m2 times in G21. Hence, Kn,n,⋯,n⏟m can be decomposed by G21.Theorem 26.
Letn≥10,m≥2 be integers. Then, there is an orthogonal labelling for
(47)G22≅∪0≤i<j≤m−1C101,0,0,0,0,0,0,0,0,n−10i,j.Proof.
SupposeVC101,0,0,0,0,0,0,0,0,n−10i,j=vs:s∈0,1,⋯,n. The mapping ψk can be used to define an orthogonal labelling for the subgraph G22, which can be defined by ψk:VC101,0,0,0,0,0,0,0,0,n−10i,j⟶ℤn×i,j which is defined by
(48)ψkv0=4i,ψkv1=6j,ψkv2=8i,ψkv3=4j,ψkv4=0i,ψkv5=0j,ψkv6=1i,ψkv7=2j,ψkv8=5i,ψkv9=8j,ψkv10=3i,ψkvs+2=sj,s∈9,10,⋯,n−2,
and the edge set ofC101,0,0,0,0,0,0,0,0,n−10i,j is
(49)EC101,0,0,0,0,0,0,0,0,n−10i,j=4i,6j,8i,6j,8i,4j,0i,4j,0i,0j,1i,0j,1i,2j,5i,2j,5i,8j∪3i,sj:s∈8,9,⋯,n−2,
see Figure24. From the edge set of G22, the following conditions are verified: Each graph C101,0,0,0,0,0,0,0,0,n−10i,j has precisely two edges of length λ∈1,2,⋯,n−1/2, the length 0 is found once in C101,0,0,0,0,0,0,0,0,n−10i,j, the length n/2 is found once in C101,0,0,0,0,0,0,0,0,n−10i,j if n is even, for every λ∈1,2,⋯,n−1/2,G22 has precisely 2.m2=mm−1 edges of length λ, the length n/2 is found m2 times in G22 if n is even, and the length 0 is found m2 times in G22. Hence, Kn,n,⋯,n⏟mcan be decomposed by G22.Figure 16
The labelling forC21,n−2i,j.Figure 17
The labelling forC31,0,n−3i,j.Figure 18
The labelling forC41,0,0,n−4i,j.Figure 19
The labelling forC51,0,0,0,n−5i,j.Figure 20
The labelling forC61,0,0,0,0,n−6i,j.Figure 21
The labelling forC71,0,0,0,0,0,n−7i,j.Figure 22
The labelling forC81,0,0,0,0,0,0,n−8i,j.Figure 23
The labelling forC91,0,0,0,0,0,0,0,n−9i,j.Figure 24
The labelling forC101,0,0,0,0,0,0,0,0,n−10i,j.


## 5. Conclusion

As known, there are several types of graphs labelling. Herein, we are concerned with orthogonal labelling notion. As a generalization to the orthogonal labelling approach provided in the literature for finding the decomposition of circulant-balanced complete bipartite graphsKn,n, we have developed a generalized orthogonal labelling approach for decomposing the circulant-balanced complete multipartite graphs Kn,n,⋯,n⏟m;m,n≥2, in this study. In the future, we will work to improve the orthogonal labelling approach so that it may be used with all types of circulant graphs.



---

*Source: 2017936-2022-07-18.xml*