# A Novel Approach for Cyclic Decompositions of Balanced Complete Bipartite Graphs into Infinite Graph Classes

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

---

## Abstract

Graph theory is considered an attractive field for finding the proof techniques in discrete mathematics. The results of graph theory have applications in many areas of social, computing, and natural sciences. Graph labelings and decompositions have received much attention in the literature. Several types of graph labeling were proposed for solving the problem of decomposing different graph classes. In the present paper, we propose a technique for labeling the vertices of a bipartite graphG with n edges, called orthogonal labeling, to yield cyclic decompositions of balanced complete bipartite graphs Kn,n by the graph G. By applying the proposed orthogonal labeling technique, we had constructed decompositions of Kn,n by paths, trees, one factorization, disjoint union of cycles, complete bipartite graphs, disjoint union of trees, caterpillars, and so forth. From the constructed results, we can confirm that the proposed orthogonal labeling technique is effective.


---

## Body

## 1. Introduction

To begin with, we summarize the main nomenclatures that will be used in this paper, which are listed in Table1.Table 1
Nomenclatures that are used in this paper.
KrComplete graph withr vertices.Ks,tComplete bipartite graph with parts of cardinalitiess and t.F∪GDisjoint union of graphsF and G.PrPath graph onr vertices.CrCycle graph onr vertices.VFVertex set of graphF.EFEdge set of graphF.lFl isolated copies of graph F.ℤnThe group of integers modulon.All graphs handled in this paper are simple (no loops or multiple edges). We refer the reader to [1] for any undefined terms. A graph labeling is a mapping that usually carries vertices and/or edges of a graph into a set of integers. Several kinds of labeling have been investigated; there is an excellent survey of graph labeling [2]. Sedlacek introduced the magic labeling of graphs [3], and the magic total labeling for the graph vertices first showed up in [4]. The super vertex magic total labeling notion was introduced by MacDougall et al. [5]. Emonoto et al. presented the notion of super edge-magic graphs [6]. Some results, concerned with super edge-magic total graphs, were introduced in [7]. The concepts of a V-super vertex magic labeling were handled by several authors [8, 9]. General results were presented in [10].Definition 1.
A graphG is a subgraph of a graph HifVG⊆VHandEG⊆EH.Definition 2.
Two simple graphsG and F are isomorphic (G≅F) if there is a bijection π:VG⟶VF such that a,b∈EG if and only if πa,πb∈EF.Graph decompositions have been and remain the focus of a great deal of research [11]. A decomposition of any graph H, by a graph G, is a collection F of isomorphic subgraphs Gx1≤x≤n, called a G-decomposition of H, where EGx:1≤x≤n is a partition of the edge set EH of H. In [12], Alspach asked about the possibility of having a cycle decomposition of complete graphs. Several papers were devoted to solving this problem [13–15]. A graph G is bipartite iff VG is composed of two disjoint independent sets of vertices called partite sets of G. Several kinds of graph decompositions appeared in the literature of graph theory. Among them, graph decompositions by bipartite graphs [16–19] were studied. Graph decompositions have interesting and many applications in different areas of computer science and combinatorics. Decompositions of complete bipartite graphs by cycles have also been studied in the literature [20–24]. Bipartite graphs can be used for modeling many systems. An increasing attention has been paid to such graphs, such as the disease analysis [25], controllability [26, 27], personal recommendation [28], link prediction [29], and community detection [30]. Factorizations of cyclic type for complete bipartite graphs into hypercubes were introduced in [31]. Decompositions of complete and complete bipartite graphs into cubes were proved in [32]. Cichacz et al. introduced the decomposition of complete bipartite graphs by generalized prisms [33]. Balanced complete bipartite graphs were decomposed by suns and stars in [34]. Hamilton cycle and path decompositions of complete bipartite graphs were investigated in [35]. In [36], the authors handled the decomposition of complete bipartite graphs by cycles of distinct even lengths. In [37], the authors proposed the decomposition of bipartite circulant graphs using algorithmic approaches. There are new applications for the decompositions of balanced complete bipartite graphs that appeared in [38, 39].Motivated by the abovementioned results, based on the orthogonal labeling technique, we can construct several edge decompositions of balanced complete bipartite graphs by infinite graph classes. In order to show the effectiveness of the orthogonal labeling technique, we find several decompositions by paths, trees, cycles, complete bipartite graphs, caterpillars, and so forth. Our study is organized as follows. Section2 addresses the proposed approach of orthogonal labeling. We introduce decompositions of balanced complete bipartite graphs by infinite graph classes in Section 3. Section 4 gives decompositions of balanced complete bipartite graphs by caterpillars. Finally, in Section 5, we introduce the conclusion and future works.


## 2. Proposed Approach

In what follows, we will show the proposed approach for constructing the edge decomposition of balanced complete bipartite graphs. Consider now the balanced complete bipartite graph with vertex setV=V1∪V2, where V1 and V2 are two independent sets of vertices. There is a bijective mapping ψ:V⟶ℤn×ℤ2, where the vertices in V1 are labeled by ℤn×0, and the vertices in V2 are labeled by ℤn×1. The distance between two vertices x0∈00,10,⋯,n−10 and y1∈01,11,⋯,n−11 is the usual circular distance defined by dx0,y1=minx−y,n−x−y. The edge x0,y1 is said to have length dx0,y1. Given a subgraph G=V,E with 2n vertices and n edges (isolated vertices are permitted), a labeling φ:V⟶ℤn×ℤ2 is an orthogonal labeling of G if, for every λ∈1,2,⋯,n−1/2,G has precisely a pair of edges of length λ, the length 0 is only present once, and the length n/2 is only present once if n is even.Example 1.
An orthogonal labeling of the pathP5 is obtained if we label the vertices consecutively with 00,01,10,31,20. Indeed, the edges 00,11 and 30,21 have length 1, the edge 00,11 has length 0, and the edge 30,11 has length 2. Similarly, we obtain an orthogonal labeling of the path P7 by labeling the vertices consecutively with 01,00,11,50,21,40,31.Definition 3.
LetG be a subgraph of Kn,n,x∈ℤn. Then, the subgraph G+x with EG+x=a+x,b+x:a,b∈EGis called thex-translate ofG.The next theorem relates the edge decomposition of complete bipartite graphs and orthogonal labeling.Theorem 4.
An edge decomposition ofKn,n by a subgraph G exists if and only if there exists an orthogonal labeling of G..Proof.
We want to prove thatEG+ω∩EG+σ=ϕ for all ω,σ∈ℤn. By the way of contradiction, we assume that EG+ω∩EG+σ≥1 for ω,σ∈ℤn with ω≠σ. For the lengths λ∈1,2,⋯,n−1/2, which are repeated twice in G, let a,b and c,d be two edges of EG+ω∩EG+σ with length λ, then a−ω,b−ω,c−ω,d−ω and a−σ,b−σ,c−σ,d−σ are different edges in EG having length λ. But this is a contradiction, since G has an orthogonal labeling. For the lengths 0 and n/2 (when n is even) which are found once in G, let a,b be an edge of EG+ω∩EG+σ with length λ, then a−ω,b−ω and a−σ,b−σ are different edges in EG, both having length λ. But this is a contradiction, since G has an orthogonal labeling.Example 2.
An edge decomposition ofK5,5 by G≅P6 is shown in Figure 1.Figure 1
An edge decomposition ofK5,5 by P6.


## 3. Decompositions ofKn,n by Infinite Graph Classes

This section is devoted to prove the existence of several edge decompositions ofKn,n which are based on the orthogonal labeling notion of different graphs.Theorem 5.
Letn be an even integer, then there is an edge decomposition of Kn,n by n/2K1,2.Proof.
Let the vertex set ofn/2K1,2 be Vn/2K1,2=vi:i∈0,1,2,⋯,2n−1. An orthogonal labeling of the subgraph n/2K1,2 can be defined by the mapping φ:Vn/2K1,2⟶ℤn×ℤ2 which is defined by φvi=i0,i∈0,1,⋯,n−1,φvn+i=2imodn1,i∈0,1,⋯,n−1, and the edge set of n/2K1,2 is En/2K1,2=i0,2imodn1:i∈0,1,2,⋯,n−1, see Figure 2. It is straightforward to check that for every λ∈1,2,⋯,n−1/2,n/2K1,2 has precisely a pair of edges of length λ, the length 0 is only present once, and the length n/2 is only present once. Consequently, there is an edge decomposition of Kn,n by n/2K1,2.Theorem 6.
Letn be an odd integer, then there is an edge decomposition of Kn,n by Pn+1.Proof.
Let the vertex set ofPn+1 be VPn+1=vi:i∈0,1,2,⋯,n. An orthogonal labeling of the subgraph Pn+1 can be defined by the mapping φ:VPn+1⟶ℤn×ℤ2 which is defined by φvi=n−imodn0,i∈0,1,⋯,n−3/2,φvn−1/2=n+1/20,φvn−3/2+i+2=i1,i∈0,1,⋯,n−1/2,and the edge set of Pn+1 is
(1)EPn+1=n+1/20,n−1/21∪n−imodn0,i+α1:i∈0,1,⋯,n−3/2,α∈0,1,see Figure 3. It is straightforward to check that for every λ∈1,2,⋯,n−1/2,Pn+1 has precisely a pair of edges of length λ, the length 0 is only present once. Consequently, there is an edge decomposition of Kn,n by Pn+1.Theorem 7.
Letn≡1mod6,n≡5mod6, then there is an edge decomposition of Kn,n by nK1,1.Proof.
Let the vertex set ofnK1,1 be VnK1,1=vi:i∈0,1,2,⋯,2n−1. An orthogonal labeling of the subgraph nK1,1 can be defined by the mapping φ:VnK1,1⟶ℤn×ℤ2 which is defined by φvi=i0,i∈0,1,⋯,n−1,φvn+i−1=2i−1modn1,i∈1,2,⋯,n, and the edge set of nK1,1 is EnK1,1=i0,2imodn1:i∈0,1,⋯,n−1, see Figure 4. It is straightforward to check that for every λ∈1,2,⋯,n−1/2,nK1,1 has precisely a pair of edges of length λ, the length 0 is only present once. Consequently, there is an edge decomposition of Kn,n by nK1,1.Theorem 8.
Letn be an integer, then there is an edge decomposition of K4n,4n by nC4, where gcdn,3=1.Proof.
Let the vertex set ofnC4 be VnC4=vi:i∈0,1,2,⋯,4n−1. An orthogonal labeling of the subgraph nC4 can be defined by the mapping φ:VnC4⟶ℤ4n×ℤ2 which is defined by φvi=i0,i∈0,1,⋯,2n−1,φv2n+i=2imod4n1,i∈0,1,⋯,2n−1, and the edge set of nC4 is EnC4=i0,2i1:i∈0,1,⋯,2n−1∪i−2n0,2i−2nmod4n1:i∈2n,⋯,4n−1.It is straightforward to check that for every λ∈1,2,⋯,4n−1/2,nC4 has precisely a pair of edges of length λ, the length 0 is only present once, and the length 2n is only present once. Consequently, there is an edge decomposition of K4n,4n by nC4.Example 3.
An orthogonal labeling of the path2C4 is shown in Figure 5.Theorem 9.
Letn be an integer, then there is an edge decomposition of K2n,2n by K2,n.Proof.
Let the vertex set ofK2,n be VK2,n=vi:i∈0,1,2,⋯,n+1. An orthogonal labeling of the subgraph K2,n can be defined by the mapping φ:VK2,n⟶ℤ2n×ℤ2 which is defined by φvi=i0,i∈0,1,φvi+2=2i−1mod2n1,i∈1,⋯,n, and the edge set of K2,n is EK2,n=00,2i1:i∈0,1,⋯,n−1∪10,2imod2n1:i∈1,⋯,n,see Figure 6. It is straightforward to check that for every λ∈1,2,⋯,2n−1/2,K2,n has precisely a pair of edges of length λ, the length 0 is only present once, and the length n is only present once. Consequently, there is an edge decomposition of K2n,2n by K2,n.Theorem 10.
Letn be integer such that n≥5. Then, there is an edge decomposition of Kn,n by 2K1,1∪K1,n−2.Proof.
Let the vertex set of2K1,1∪K1,n−2 be V2K1,1∪K1,n−2=vi:i∈0,1,2,⋯,n+2. An orthogonal labeling of the subgraph 2K1,1∪K1,n−2 can be defined by the mapping φ:V2K1,1∪K1,n−2⟶ℤn×ℤ2 which is defined by
(2)φv0=00,φv1=10,φv2=n−10,φvi+3=i1,i∈0,⋯,n−1,and the edge set of 2K1,1∪K1,n−2 is
(3)E2K1,1∪K1,n−2=00,i1:i∈0,1,⋯,n−3∪10,n−11,n−10,n−21,see Figure 7. It is straightforward to check that for every λ∈1,2,⋯,n−1/2,2K1,1∪K1,n−2 has precisely a pair of edges of length λ, the length 0 is only present once, and the length n/2 is only present once if n is even. Consequently, there is an edge decomposition of K2n,2n by 2K1,1∪K1,n−2.Theorem 11.
Letn be an odd integer such that n>5. Then, there is an edge decomposition of Kn,n by K2,2∪K1,n−4.Proof.
Let the vertex set ofK2,2∪K1,n−4 be VK2,2∪K1,n−4=vi:i∈0,1,2,⋯,n. An orthogonal labeling of the subgraph K2,2∪K1,n−4 can be defined by the mapping φ:VK2,2∪K1,n−4⟶ℤn×ℤ2 which is defined by
(4)φv0=n+320,φv1=n−120,φv2=n+120,φvi+3=n−12+i1,i∈0,⋯,n−5,and the edge set of K2,2∪K1,n−4 is EK2,2∪K1,n−4=n+3/20,n1,n+3/20,n+11,n−1/20,n1,n−1/20,n+11,n+1/20,n−1/21∪n+1/20,n+1/2+i1:i∈0,1,⋯,n−6, see Figure 8. It is straightforward to check that for everyλ∈1,2,⋯,n−1/2,K2,2∪K1,n−4 has precisely a pair of edges of length λ, the length 0 is only present once. Consequently, there is an edge decomposition of Kn,n by K2,2∪K1,n−4.Theorem 12.
Letn be an integer such that n≥9. Then, there is an edge decomposition of Kn,n by C8∪K1,n−8.Proof.
Let the vertex set ofC8∪K1,n−8 be VC8∪K1,n−8=vi:i∈0,1,2,⋯,n. An orthogonal labeling of the subgraph C8∪K1,n−8 can be defined by the mapping φ:VC8∪K1,n−8⟶ℤn×ℤ2 which is defined by φv0=00,φv1=10,φv2=20,φv3=40,φv4=80,φvi=i−41,i∈5,⋯,n, and the edge set of C8∪K1,n−8 isEC8∪K1,n−8=00,21,00,41,40,21,40,31,20,31,20,51,80,41,80,51,10,11∪10,i1:i∈6,7,⋯,n−4,
∪10,i1:i∈6,7,⋯,n−4, see Figure 9. It is straightforward to check that for every λ∈1,2,⋯,n−1/2,C8∪K1,n−8 has precisely a pair of edges of length λ, the length 0 is only present once, and the length n/2 is only present once if n is even. Consequently, there is an edge decomposition of Kn,n by C8∪K1,n−8.Theorem 13.
Letn be an integer such that n>7. Then, there is an edge decomposition of Kn,n by K1,1∪C6∪K1,n−7.Proof.
Let the vertex set ofK1,1∪C6∪K1,n−7 be VK1,1∪C6∪K1,n−7=vi:i∈0,1,2,⋯,n. An orthogonal labeling of the subgraph K1,1∪C6∪K1,n−7 can be defined by the mapping φ:VK1,1∪C6∪K1,n−7⟶ℤn×ℤ2 which is defined by φv0=00,φv1=10,φv2=30,φv3=40,φv4=60,φv5=11,φv6=21,φv7=31,φv8=51,φvi=i−21,i∈9,⋯,n+1, and the edge set of K1,1∪C6∪K1,n−7 is EK1,1∪C6∪K1,n−7=10,11,00,21,00,31,40,21,40,51,60,31,60,51∪30,i1:i∈7,⋯,n−1, see Figure 10. It is straightforward to check that for every λ∈1,2,⋯,n−1/2,K1,1∪C6∪K1,n−7 has precisely a pair of edges of length λ, the length 0 is only present once, and the length n/2 is only present once if n is even. Hence, there is an edge decomposition of Kn,n by K1,1∪C6∪K1,n−7.Theorem 14.
Letn be an integer such that n≥1. Then, there is an edge decomposition of K4n+2,4n+2 by K1,2∪K2,2n.Proof.
Let the vertex set ofK1,2∪K2,2n be VK1,2∪K2,2n=vi:i∈0,1,2,⋯,2n+4. An orthogonal labeling of the subgraph K1,2∪K2,2n can be defined by the mapping φ:VK1,2∪K2,2n⟶ℤ4n+2×ℤ2 which is defined by φv0=4n+10,φv1=2n0,φv2=00,φv3=2n+10,φv4=4n+11,φvi=n+i−41,i∈5,⋯,n+4,φvn+i=2n+i−31,i∈5,⋯,n+4, and the edge set of K1,2∪K2,2n is EK1,2∪K2,2n=4n+10,4n+11,2n0,4n+11∪00,i1,2n+10,i1:i∈n+1,⋯,2n∪00,i1,2n+10,i1,i∈2n+2,⋯,3n+1, see Figure 11. It is straightforward to check that for every λ∈1,2,⋯,4n+1/2,K1,2∪K2,2n has precisely a pair of edges of length λ, the length 0 is only present once, and the length 2n+1 is only present once. Consequently, there is an edge decomposition of K4n+2,4n+2 by K1,2∪K2,2n.Theorem 15.
Letn be an integer such that n≥3. Then, there is an edge decomposition of K3n,3n by K3,n.Proof.
Let the vertex set ofK3,n be VK3,n=vi:i∈0,1,2,⋯,2n+4. An orthogonal labeling of the subgraph K3,n can be defined by the mapping φ:VK3,n⟶ℤ3n×ℤ2 which is defined by φv0=00,φv1=20,φv2=40,φvi=3i−31,i∈3,⋯,n+2, and the edge set of K3,n is EK3,n=i0,j1:i∈0,2,4,j∈0,3,6,⋯,3n−3, see Figure 12. It is straightforward to check that for every λ∈1,2,⋯,3n−1/2,K3,n has precisely a pair of edges of length λ, the length 0 is only present once, and the length 3n/2 is only present once if n is even. Consequently, there is an edge decomposition of K3n,3n by K3,n.Theorem 16.
Letn be an integer such that n≥4. Then, there is an edge decomposition of K2n+1,2n+1 by K1,1∪K1,2∪K1,4∪K1,2n‐6.Proof.
Let the vertex set ofK1,1∪K1,2∪K1,4∪K1,2n‐6 be VK1,1∪K1,2∪K1,4∪K1,2n‐6=vi:i∈0,1,2,⋯,2n+4. An orthogonal labeling of the subgraph K1,1∪K1,2∪K1,4∪K1,2n‐6 can be defined by the mapping
(5)φ:VK1,1∪K1,2∪K1,4∪K1,2n‐6⟶ℤ2n+1×ℤ2,which is defined by
φv0=30,φv1=2n−30,φv2=20,φv3=00,φv4=2n0,φv5=31,φv6=2n1,φv7=01,φv8=11,φv9=2n−21,φv10=2n−11,φvi+1=i−61,i∈10,⋯,2n+3, and the edge set of K1,1∪K1,2∪K1,4∪K1,2n‐6 is EK1,1∪K1,2∪K1,4∪K1,2n‐6=30,31,2n−30,2n1,20,2n1,2n0,01,2n0,11,2n0,2n−21,2n0,2n−11∪00,j1:j∈4,5,⋯,2n−3, see Figure 13. It is straightforward to check that for every λ∈1,2,⋯,n,K1,1∪K1,2∪K1,4∪K1,2n‐6 has precisely a pair of edges of length λ, the length 0 is only present once. Consequently, there is an edge decomposition of K2n+1,2n+1 by K1,1∪K1,2∪K1,4∪K1,2n‐6.Theorem 17.
Letn be an integer such that n≥2. Then, there is an edge decomposition of K2n,2n by 2K1,n.Proof.
Let the vertex set of2K1,n be V2K1,n=vi:i∈0,1,2,⋯,2n+1. An orthogonal labeling of the subgraph 2K1,n can be defined by the mapping φ:V2K1,n⟶ℤ2n×ℤ2 which is defined by φv0=n−20,φv1=n0,φvi+2=i1,i∈0,⋯,2n−1, and the edge set of 2K1,n is E2K1,n=n0,2i+11,n−20,2i1:i∈0,1,⋯,n−1, see Figure 14. It is straightforward to check that for every λ∈1,2,⋯,2n−1/2,2K1,n has precisely a pair of edges of length λ, the length 0 is only present once, the length n is only present once. Hence, there is an edge decomposition of K2n,2n by 2K1,n.Figure 2
An orthogonal labeling forn/2K1,2.Figure 3
An orthogonal labeling forPn+1.Figure 4
An orthogonal labeling fornK1,1.Figure 5
An orthogonal labeling for2C4.Figure 6
An orthogonal labeling forK2,n.Figure 7
An orthogonal labeling for2K1,1∪K1,n−2.Figure 8
An orthogonal labeling forK2,2∪K1,n−4.Figure 9
An orthogonal labeling forC8∪K1,n−8.Figure 10
An orthogonal labeling forK1,1∪C6∪K1,n−7.Figure 11
An orthogonal labeling forK1,2∪K2,2n.Figure 12
An orthogonal labeling forK3,n.Figure 13
An orthogonal labeling forK1,1∪K1,2∪K1,4∪K1,2n‐6.Figure 14
An orthogonal labeling for2K1,n.


## 4. Decompositions ofKn,n by Caterpillars

Definition 18.
The caterpillar graphCrm1,m2,⋯,mr is a tree obtained from the path Pr=y1y2⋯yr by joining vertex yi to mi new vertices where r≥1,m1,m2,⋯,mr are positive integers, m1,mr≥1 and mi≥0 for i∈2,3,⋯,r−1.Theorem 19.
Letn be an integer such that n≥2. Then, there is an edge decomposition of Kn,n by C21,n−2.Proof.
Let the vertex set ofC21,n−2 be VC21,n−2=vi:i∈0,1,⋯,n. An orthogonal labeling of the subgraph C21,n−2 can be defined by the mapping φ:VC21,n−2⟶ℤn×ℤ2 which is defined by φv0=00,φv1=10,φv2=01,φvi=i−11,i∈3,4,⋯,n, and the edge set of C21,n−2 is EC21,n−2=00,01,10,01∪10,i1:i∈2,3,⋯,n−1, see Figure 15. It is straightforward to check that for every λ∈1,2,⋯,n−1/2,C21,n−2 has precisely a pair of edges of length λ, the length 0 is only present once, and the length n/2 is only present once if n is even. Hence, there is an edge decomposition of Kn,n by C21,n−2.Theorem 20.
Letn be an integer such that n≥3. Then, there is an edge decomposition of Kn,n by C31,0,n−3.Proof.
Let the vertex set ofC31,0,n−3 be VC31,0,n−3=vi:i∈0,1,⋯,n. An orthogonal labeling of the subgraph C31,0,n−3 can be defined by the mapping φ:VC31,0,n−3⟶ℤn×ℤ2 which is defined by
(6)φv0=00,φv1=n−10,φv2=01,φv3=11,φvi=i−11,i∈4,5,⋯,n,and the edge set of C31,0,n−3 is
(7)EC31,0,n−3=00,01,n−10,01,n−10,11∪00,i1:i∈3,4,⋯,n−1,see Figure 16. It is straightforward to check that for every λ∈1,2,⋯,n−1/2,C31,0,n−3 has precisely a pair of edges of length λ, the length 0 is only present once, and the length n/2 is only present once if n is even. Consequently, there is an edge decomposition of Kn,n by C31,0,n−3.Theorem 21.
Letn be an integer such that n≥4. Then, there is an edge decomposition of Kn,n by C41,0,0,n−4.Proof.
Let the vertex set ofC41,0,0,n−4 be VC41,0,0,n−4=vi:i∈0,1,⋯,n. An orthogonal labeling of the subgraph C41,0,0,n−4 can be defined by the mapping φ:VC41,0,0,n−4⟶ℤn×ℤ2 which is defined by
(8)φv0=00,φv1=n−10,φv2=01,φv3=11,φv4=n−21,φvi+3=i0,i∈2,3,⋯,n−3,
and the edge set ofC41,0,0,n−4 is
(9)EC41,0,0,n−4=00,01,00,11,n−10,n−21,n−10,11∪i0,01:i∈2,3,⋯,n−3,
see Figure17. It is straightforward to check that for every λ∈1,2,⋯,n−1/2,C41,0,0,n−4 has precisely a pair of edges of length λ, the length 0 is only present once, and the length n/2 is only present once if n is even. Hence, there is an edge decomposition of Kn,n by C41,0,0,n−4.Theorem 22.
Letn be an integer such that n≥5. Then, there is an edge decomposition of Kn,n by C51,0,0,0,n−5.Proof.
Let the vertex set ofC51,0,0,0,n−5 be VC51,0,0,0,n−5=vi:i∈0,1,⋯,n. An orthogonal labeling of the subgraph C51,0,0,0,n−5 can be defined by the mapping φ:VC51,0,0,0,n−5⟶ℤn×ℤ2 which is defined by
(10)φv0=01,φv1=00,φv2=21,φv3=40,φv4=31,φv5=20,φvi+1=i1,i∈5,6,⋯,n−1,
and the edge set ofC51,0,0,0,n−5 is
(11)EC51,0,0,0,n−5=00,01,20,31,00,21,40,21,40,31∪20,i1:i∈5,6,⋯,n−1,
see Figure18. It is straightforward to check that for every λ∈1,2,⋯,n−1/2,C51,0,0,0,n−5 has precisely a pair of edges of length λ, the length 0 is only present once, and the length n/2 is only present once if n is even. Hence, there is an edge decomposition of Kn,n by C51,0,0,0,n−5.Theorem 23.
Letn be an integer such that n≥6. Then, there is an edge decomposition of Kn,n by C61,0,0,0,0,n−6.Proof.
Let the vertex set ofC61,0,0,0,0,n−6 be VC61,0,0,0,0,n−6=vi:i∈0,1,⋯,n. An orthogonal labeling of the subgraph C61,0,0,0,0,n−6 can be defined by the mapping φ:VC61,0,0,0,0,n−6⟶ℤn×ℤ2 which is defined by φv0=01,φv1=n−10,φv2=n−21,φv3=00,φv4=21,φv5=20,φv6=n−11,φvi+4=i0,i∈3,4,⋯,n−4, and the edge set of C61,0,0,0,0,n−6 is EC61,0,0,0,0,n−6=n−10,01,n−10,n−21,00,n−21,00,21,20,21,20,n−11∪i0,n−11:i∈3,4,⋯,n−4, see Figure 19. It is straightforward to check that for every λ∈1,2,⋯,n−1/2,C61,0,0,0,0,n−6 has precisely a pair of edges of length λ, the length 0 is only present once, and the length n/2 is only present once if n is even. Hence, there is an edge decomposition of Kn,n by C61,0,0,0,0,n−6.Theorem 24.
Letn be an integer such that n≥7. Then, there is an edge decomposition of Kn,n by C71,0,0,0,0,0,n−7.Proof.
Let the vertex set ofC71,0,0,0,0,0,n−7 be VC71,0,0,0,0,0,n−7=vi:i∈0,1,⋯,n. An orthogonal labeling of the subgraph C71,0,0,0,0,0,n−7 can be defined by the mapping φ:VC71,0,0,0,0,0,n−7⟶ℤn×ℤ2 which is defined by φv0=21,φv1=10,φv2=01,φv3=00,φv4=31,φv5=60,φv6=41,φv7=20,φvi+2=i1,i∈6,7,⋯,n−2, and the edge set of C71,0,0,0,0,0,n−7 is EC71,0,0,0,0,0,n−7=10,21,10,01,00,01,00,31,60,31,60,41,20,41∪20,i1:i∈6,7,⋯,n−2, see Figure 20. It is straightforward to check that for every λ∈1,2,⋯,n−1/2,C71,0,0,0,0,0,n−7 has precisely a pair of edges of length λ, the length 0 is only present once, and the length n/2 is only present once if n is even. Hence, there is an edge decomposition of Kn,n by C71,0,0,0,0,0,n−7.Theorem 25.
Letn be an integer such that n≥8. Then, there is an edge decomposition of Kn,n by C81,0,0,0,0,0,0,n−8.Proof.
Let the vertex set ofC81,0,0,0,0,0,0,n−8 be VC81,0,0,0,0,0,0,n−8=vi:i∈0,1,⋯,n. An orthogonal labeling of the subgraph C81,0,0,0,0,0,0,n−8 can be defined by the mapping φ:VC81,0,0,0,0,0,0,n−8⟶ℤn×ℤ2 which is defined by φv0=60,φv1=51,φv2=40,φv3=21,φv4=00,φv5=01,φv6=30,φv7=61,φv8=20,φvi+2=i1,i∈7,8,⋯,n−2, and the edge set of C81,0,0,0,0,0,0,n−8 is EC81,0,0,0,0,0,0,n−8=60,51,40,21,00,21,00,01,30,01,30,61,20,61∪20,i1:i∈7,8,⋯,n−2, see Figure 21. It is straightforward to check that for every λ∈1,2,⋯,n−1/2,C81,0,0,0,0,0,0,n−8 has precisely a pair of edges of length λ, the length 0 is only present once, and the length n/2 is only present once if n is even. Hence, there is an edge decomposition of Kn,n by C81,0,0,0,0,0,0,n−8.Theorem 26.
Letn be an integer such that n≥9. Then, there is an edge decomposition of Kn,n by C91,0,0,0,0,0,0,0,n−9.Proof.
Let the vertex set ofC91,0,0,0,0,0,0,0,n−9 be VC91,0,0,0,0,0,0,0,n−9=vi:i∈0,1,⋯,n. An orthogonal labeling of the subgraph C91,0,0,0,0,0,0,0,n−9 can be defined by the mapping φ:VC91,0,0,0,0,0,0,0,n−9⟶ℤn×ℤ2 which is defined by φv0=61,φv1=40,φv2=21,φv3=10,φv4=01,φv5=00,φv6=41,φv7=80,φv8=51,φv9=20,φvi+3=i1,i∈7,8,⋯,n−3, and the edge set of C91,0,0,0,0,0,0,0,n−9 is EC91,0,0,0,0,0,0,0,n−9=40,61,40,21,10,21,10,01,00,01,00,41,80,41,80,51,20,51,∪20,i1:i∈7,8,⋯,n−3, see Figure 22. It is straightforward to check that for every λ∈1,2,⋯,n−1/2,C91,0,0,0,0,0,0,0,n−9 has precisely a pair of edges of length λ, the length 0 is only present once, and the length n/2 is only present once if n is even. Hence, there is an edge decomposition of Kn,n by C91,0,0,0,0,0,0,0,n−9.Theorem 27.
Letn be an integer such that n≥10. Then, there is an edge decomposition of Kn,n by C101,0,0,0,0,0,0,0,0,n−10.Proof.
Let the vertex set ofC101,0,0,0,0,0,0,0,0,n−10 be VC101,0,0,0,0,0,0,0,0,n−10=vi:i∈0,1,⋯,n. An orthogonal labeling of the subgraph C101,0,0,0,0,0,0,0,0,n−10 can be defined by the mapping φ:VC101,0,0,0,0,0,0,0,0,n−10⟶ℤn×ℤ2 which is defined by φv0=40,φv1=61,φv2=80,φv3=41,φv4=00,φv5=01,φv6=10,φv7=21,φv8=50,φv9=81,φv10=30,φvi+2=i1,i∈9,10,⋯,n−2, and the edge set of C101,0,0,0,0,0,0,0,0,n−10 is EC101,0,0,0,0,0,0,0,0,n−10=40,61,80,61,80,41,00,41,00,01,10,01,10,21,50,21,50,81∪30,i1:i∈8,9,⋯,n−2, see Figure 23. It is straightforward to check that for every λ∈1,2,⋯,n−1/2,C101,0,0,0,0,0,0,0,0,n−10 has precisely a pair of edges of length λ, the length 0 is only present once, and the length n/2 is only present once if n is even. Hence, there is an edge decomposition of Kn,n by C101,0,0,0,0,0,0,0,0,n−10.Figure 15
An orthogonal labeling forC21,n−2.Figure 16
An orthogonal labeling forC31,0,n−3.Figure 17
An orthogonal labeling forC41,0,0,n−4.Figure 18
An orthogonal labeling forC51,0,0,0,n−5.Figure 19
An orthogonal labeling forC61,0,0,0,0,n−6.Figure 20
An orthogonal labeling forC71,0,0,0,0,0,n−7.Figure 21
An orthogonal labeling forC81,0,0,0,0,0,0,n−8.Figure 22
An orthogonal labeling forC91,0,0,0,0,0,0,0,n−9.Figure 23
An orthogonal labeling forC101,0,0,0,0,0,0,0,0,n−10.


## 5. Conclusion

In this paper, we have successfully applied the orthogonal labeling notion to construct the decomposition of balanced complete bipartite graphs by infinite graph classes, such as paths, cycles, one factorization, complete bipartite graphs, disjoint union of trees, caterpillars, and so forth. From the constructed results, we can confirm that the proposed orthogonal labeling technique is effective. Here, we have concentrated on the orthogonal labeling of bipartite graphs. In future works, we will try to generalize the orthogonal labeling notion to other several classes of graphs.



---

*Source: 9308708-2022-05-04.xml*