Decomposition of Complete Tripartite Graphs into Short Cycles

Arputha Jose. T.1, Sampath Kumar S.1, Cecily Sahai C.1
1Department of Mathematics, Sri Sivasubramaniya Nadar College of Engineering, Kalavakkam, Chennai – 603110, India

Abstract

For a graph G and for non-negative integers p,q and r, the triplet (p,q,r) is said to be an admissible triplet, if 3p+4q+6r=|E(G)|. If G admits a decomposition into p cycles of length 3, q cycles of length 4, and r cycles of length 6 for every admissible triplet (p,q,r), then we say that G has a {C3p,C4q,C6r}-decomposition. In this paper, the necessary conditions for the existence of {C3p,C4q,C6r}-decomposition of K,m,n(mn) are proved to be sufficient. This affirmatively answers the problem raised in \emph{Decomposing complete tripartite graphs into cycles of lengths 3 and 4, Discrete Math. 197/198 (1999), 123-135}. As a corollary, we deduce the main results of \emph{Decomposing complete tripartite graphs into cycles of lengths 3 and 4, Discrete Math., 197/198, 123-135 (1999)} and \emph{Decompositions of complete tripartite graphs into cycles of lengths 3 and 6, Austral. J. Combin., 73(1), 220-241 (2019)}.

Keywords: Cycle decompositions, Latin square, Complete tripartite graphs

1. Introduction

All graphs considered here are simple, finite and undirected. Let Km and Cm denote the complete graph and a cycle on m vertices. Let Pm+1 denotes a path on m edges. If H1,H2,,Hn are edge disjoint subgraphs of G such that E(G)=E(H1)E(H2)E(Hn), where denotes the disjoint union of graphs, then we say that H1,H2,,Hn decomposes G. If each HiH, then we say that H decomposes G and it is denoted by H|G. If each H is a cycle Cm, then we say that G admits a Cm-decomposition or m-cycle decomposition and is denoted by Cm|G. For non-negative integers p,q and r, the triplet (p,q,r) is said to be an admissible triplet for the graph G, if 3p+4q+6r=|E(G)|. Similarly, the triplet (p,q,r) is said to be an admissible triplet for the sub-graph H, if 3p+4q+6r=|E(H)|. If G admits a decomposition into p cycles of length 3, q cycles of length 4 and r cycles of length 6 for every admissible triplets (p,q,r), then we say that G has a {C3p,C4q,C6r}-decomposition. For terms not defined here one can refer to [1,2].

A latin square of order n is a n×n array, each cell of which contains exactly one of the symbols in {1,2,,n}, such that each row and each column of the array contains each of the symbols in {1,2,,n} exactly once. A latin square is said to be idempotent if the cell (i,i) contains the symbol i,1in. A latin square of order n is said to be cyclic if it’s first row entries are a1,a2,,an, then the pth row entries are ap,ap+1,ap+2,,ap1 in order, where the subscripts are taken modulo n with residues 1,2,,n, see [3]. A latin square is said to be a latin rectangle, if there exists a rectangular ×m array with entries from the set N={1,2,,n} such that each entry appears at most once in each row and column based on n elements [4].

It is worth mentioning that cycle decomposition problems are NP – complete in general, see [5]. Recently, Paulraja and Srimathi [6,7] proved the necessary and sufficient conditions for the existence of {C3p,C6r}-decomposition of some product of complete graphs. Ganesamurthy and Paulraja [8] gave the necessary and sufficient conditions for some classes of dense graph to admit a {C4p,C8q}-decomposition. Very recently, Ezhilarasi and Muthusamy [9], proved the necessary and sufficient conditions for the existence of {P2p+1,C2p}-decomposition of even regular complete equipartite graphs for all prime p.

The problem of decomposing complete tripartite graphs into cycles have been studied by different authors [4,10-16]. The necessary and sufficient conditions for the existence of {C3p,C4q}-decomposition of complete tripartite graph were given by Billington [17] in 1999. Recently, Ganesamurthy and Paulraja [3] proved the necessary and sufficient conditions for the existence of {C3p,C6r}-decomposition of complete tripartite graphs. Billington suggested finding the necessary and sufficient conditions for the existence of {C3p,C4q,C6r}-decomposition of K,m,n(mn). The main theorem of this paper answer this question in the affirmative.

Theorem 1. The complete tripartite graph K,m,n(mn) admits a {C3p,C4q,C6r}-decomposition if and only if the partite sets are of same parity and 3p+4q+6r=m+mn+n.

The main results of [17] can be deduced as a corollary by substituting r=0 in Theorem 1.

Corollary 1. [17]The complete tripartite graph K,m,n(mn) has an edge disjoint decomposition into p cycles of length 3 and q cycles of length 4 if and only if,

  1. ,m,n are all even or odd.

  2. If is even or if is odd and m0(mod 4), then pm.

  3. If is odd and m2(mod 4), then pm2.

  4. The value of p decreases from its maximum value in steps of size 4, down to 0 if is even and to 1, if is odd.

If we put q=0 in Theorem 1, we have the following

Corollary 2. Let K,m,n(mn) be the complete tripartite. Then this complete tripartite graph admits a {C3p,C6r}-decomposition whenever the partite sets are of same parity and 3p+6r=m+mn+n.

The corollary 2 subsumes the main result of [3].

Corollary 3. [3] Let K,m,n(mn) be the complete tripartite graph and let K,m,nK1,1,n when n1(mod6) and n>1. If mn(mod6), then K,m,n admits a {C3p,C6r}-decomposition for any p(mod2), with 0pm.

In order to prove our result, we make use of the following

Theorem 2. [18] Let m and n be positive integers. Then the complete bipartite graph K2m,2n and K2n+1,2n+1F admits a {C4p,C6q,C8r} – decomposition whenever 4p+6q+8r=|E(K2m,2n)| or 4p+6q+8r=|E(K2n+1,2n+1F)|, where F is a 1-factor of K2n+1,2n+1.

Lemma 1. [4] Let ,m and n be integers such that mn. A latin rectangle of order ×m based on n elements is equivalent to the existence of m edge-disjoint triangles sitting inside the complete tripartite graph K,m,n.

Remark 1. Since a cycle of length 3 in a {C3p,C4q,C6r}-decomposition of K,m,n(mn) needs to visit all three partite sets, in any {C3p,C4q,C6r}-decomposition of K,m,n, maximum number of 3-cycles is m.

Throughout this paper, we denote V(K,m,n)=ABC where A={a1,a2,,a}, B={b1,b2,,bm} and C={c1,c2,,cn}.

2. When Partite Sets are of Same Size

In this section, we prove the necessary conditions for the existence of {C3p,C4q,C6r}
decomposition of the complete tripartite graphs K,m,n are sufficient whenever =m=n.

Remark 2. [17] A C3-decomposition of the complete tripartite graph Km,m,m can be achieved using a latin square as follows: an entry k in the cell (i,j) corresponds to a C3, given by (ai,bj,ck) .

Lemma 2. The graph K2,2,2 admits a {C3p,C4q,C6r}-decomposition.

Proof. In this case, all the possible triplets are: (p,q,r){(4,0,0),(0,3,0),(0,0,2),(2,0,1)}. The decomposition is given below.

(4, 0, 0): (a1,b1,c2), (a1,b2,c1), (a2,b1,c1) and (a2,b2,c2).

(0, 3, 0): (a1,b2,a2,b1), (b1,c2,b2,c1) and (a1,c2,a2,c1).

(0, 0, 2): (a1,b1,c1,b2,a2,c2) and (a1,b2,c2,b1,a2,c1).

(2, 0, 1):(a1,b1,c1), (a2,b2,c2) and (a1,b2,c1,a2,b1,c2).

Thus, the graph K2,2,2 admits a {C3p,C4q,C6r}-decomposition. ◻

Lemma 3. The graph K3,3,3 admits a {C3p,C4q,C6r}-decomposition.

Proof. Consider a cyclic idempotent latin square of order 3. By Remark 2, every entry k in the latin square corresponds to a C3 in K3,3,3. For a {C3p,C4q,C6r}-decomposition of K3,3,3, it is obvious that p0, since the total number of edges is odd. We fix a C3 namely (a1,b1,c1), in all possible decompositions given below:

Now, (p,q,r){(7,0,1),(5,0,2),(5,3,0),(3,3,1),(3,0,3),(1,3,2),(1,6,0),(1,0,4)} are the set of admissible triplets in the required decomposition.

(7, 0, 1): (a1,b1,c1),(a2,b2,c3),(a1,b3,c2),(a2,b3,c1),(a3,b1,c2),(a3,b2,c1), (a3,b3,c3) and (a1,b2,c2,a2,b1,c3).

(5, 0, 2): (a1,b1,c1), (a1,b2,c2), (a2,b2,c3), (a2,b1,c2), (a3,b3,c2), (a1,b3,a2,c1,a3,c3) and (a3,b1,c3,b3,c1,b2).

(5, 3, 0): (a1,b1,c1), (a2,b3,c1), (a3,b1,c2), (a3,b2,c1), (a3,b3,c3), (a1,b2,c2,b3), (a1,c2,a2,c3) and (a2,b1,c3,b2).

(3, 3, 1): (a1,b1,c1), (a2,b1,c3), (a3,b1,c2), (a1,b2,c1,b3), (a2,b2,c2,b3), (a3,b3,c3,b2) and (a1,c2,a2,c1,a3,c3).

(3, 0, 3): (a1,b1,c1), (a1,b2,c3), (a1,b3,c2), (a2,b1,c3,a3,b2,c1), (a2,b3,c1,a3,b1,c2) and (a2,b2,c2,a3,b3,c3).

(1, 3, 2): (a1,b1,c1), (a1,b2,a2,b3), (a1,c2,b2,c3), (a2,c1,a3,c3), (a2,b1,c3,b3,a3,c2) and (a3,b1,c2,b3,c1,b2).

(1, 6, 0): (a1,b1,c1), (a1,b2,a2,b3), (a1,c2,b2,c3), (a2,c1,a3,c3), (a3,b2,c1,b3), (a2,b1,a3,c2) and (b1,c2,b3,c3).

(1, 0, 4): (a1,b1,c1), (a1,b2,a2,c1,a3,c3), (a1,b3,a2,c3,b2,c2), (a2,b1,c3,b3,a3,c2) and (a3,b1,c2,b3,c1,b2).

The above cases guarantees the existence of {C3p,C4q,C6r}-decomposition of K3,3,3 for all admissible triplets. ◻

Theorem 3. The graph K,,, admits a {C3p,C4q,C6r}-decomposition.

Proof. Let the partite sets of K,, be ABC where, A={a1,a2,,a}, B={b1,b2,,b} and {c1,c2,,c}. We consider the following two cases.

Case 1. is even.

Consider a cyclic latin square of order . This latin square is partitioned into 2×2 partial latin squares (with rows i, i+1 and columns j, j+1) of the form,

j j+1
i k k+1
i+1 k+1 k+2

The partial latin square of the above form corresponds to 12 edges and can be decomposed into 3-cycles, 4-cycles and 6-cycles for the following admissible triplets (p,q,r){(4,0,0),(2,0,1),(0,3,0),(0,0,2)}.

(4, 0, 0): The four 3-cycles can be obtained directly by using Remark 2.

(2, 0, 1): The two 3-cycles are (ai,bj,ck+1) and (ai+1,bj+1,ck+2). The required 6-cycle is (ai,ck,bj,ai+1,ck+1,bj+1).

(0, 3, 0): The required 4-cycles are given by (ai,ck,bj,ck+1), (ai,bj,ai+1,bj+1) and (ai+1,ck+1,bj+1,ck+2).

(0, 0, 2): (ai,ck,bj,ck+1,ai+1,bj+1) and (ai,ck+1,bj+1,ck+2,ai+1,bj) are the required 6-cycles.

Thus each of these 2×2 partial latin squares can be decomposed into 3, 4 and 6 cycles for all admissible triplets.

Hence K,,, where is even, admits a {C3p,C4q,C6r}-decomposition.
Case 2. is odd.

Consider a cyclic latin square of order . As is odd, p0. Hence, we fix a 3-cycle, (a1,b1,c1) that will be present in all possible decompositions. For 1i12, with the first row and first column entries of this latin square, we first partitioned the 2×2 partial latin square entries of the form,

1 2i 2i+1
1 2i 2i+1
2i 2i 4i1 4i
2i+1 2i+1 4i 4i+1

The edges corresponding to partial latin square of the above form can be decomposed into 3-cycles, 4-cycles and 6-cycles for all admissible triplets (p,q,r), where (p,q,r){(8,0,0),(6,0,1),(4,3,0),(4,0,2),(2,3,1),(2,0,3),(0,6,0),(0,0,4),(0,3,2)}.

(8, 0, 0): This can be achieved directly from Remark 2.

(6, 0, 1): (a1,b2i,c2i), (a1,b2i+1,c2i+1), (a2i,b1,c2i), (a2i+1,b1,c2i+1), (a2i,b2i,c4i), (a2i+1,b2i+1,c4i+1) and (a2i,c4i1,b2i,a2i+1,c4i,b2i+1).

(4, 3, 0): (a1,b2i,c2i), (a1,b2i+1,c2i+1), (a2i,b1,c2i), (a2i+1,b1,c2i+1), (a2i,c4i1,b2i,c4i), (a2i,b2i,a2i+1,b2i+1) and (a2i+1,c4i,b2i+1,c4i+1).

(4, 0, 2): (a1,b2i,c2i), (a1,b2i+1,c2i+1), (a2i,b1,c2i), (a2i+1,b1,c2i+1), (a2i,c4i1,b2i,c4i,a2i+1,b2i+1) and (a2i,c4i,b2i+1,c4i+1,a2i+1,b2i).

(2, 3, 1): (a2i,b2i,c2i), (a2i+1,b2i+1,c2i), (a1,b2i,c4i,b2i+1), (a1,c2i,b1,c2i+1), (a2i,b1,a2i+1,c4i) and (a2i,b2i+1,c4i+1,a2i+1,b2i,c4i1).

(2, 0, 3): (a2i,b2i,c4i), (a2i+1,b2i+1,c4i+1), (a2i,c4i1,b2i,a2i+1,c4i,b2i+1), (a1,b2i,c2i,a2i,b1,c2i+1) and (a1,b2i+1,c2i+1,a2i+1,b1,c2i).

(0, 6, 0): (a1,b2i,a2i,b2i+1), (a2i,b1,a2i+1,c4i), (a2i,c2i,b2i,c2i+1), (a2i+1,b2i,c4i,b2i+1), (a1,c2i,b1,c2i+1) and (a2i+1,c4i+1,b2i+1,c2i+1).

(0, 0, 4): (a1,b2i+1,c2i+1,a2i+1,b2i,c2i), (a1,b2i,a2i,c2i,b1,c2i+1), (a2i,b1,a2i+1,c4i+1,b2i+1,c4i) and (a2i,b2i+1,a2i+1,c4i,b2i,c4i1).

(0, 3, 2): (a2i,b2i,a2i+1,b2i+1), (a2i,c4i1,b2i,c4i), (a2i+1,c4i,b2i+1,c4i+1), (a1,b2i,c2i,a2i,b1,c2i+1) and (a1,b2i+1,c2i+1,a2i+1,b1,c2i).

The remaining entries of the latin square can be partitioned into 2×2 partial latin squares where the edges corresponding to each of the 2×2 partial latin square can be decomposed into all possible (C3,C4,C6) as in Case 1.

Hence for all admissible triplets (p,q,r), the graph K,, admits a {C3p,C4q,C6r}-decomposition. ◻

3. When Partite Sets are of Different Size

In this section, we have proved the necessary conditions for the existence of {C3p,C4q,C6r}-decomposition of the complete tripartite graphs K,m,n(mn) are sufficient.

Lemma 4. The graph K1,3,3 admits a {C3p,C4q,C6r}-decomposition.

Proof. The graph K1,3,3 has 15 edges. The maximum possible 3-cycles in the required decomposition will be three. Hence, the following are the admissible triplets (p,q,r){(3,0,1),(1,3,0),(1,0,2)}.

(3, 0, 1): (a1,b1,c1), (a1,b2,c2), (a1,b3,c3) and (b1,c2,b3,c1,b2,c3).

(1, 3, 0): (a1,b1,c1), (a1,b2,c1,b3), (a1,c2,b2,c3) and (b1,c2,b3,c3).

(1, 0, 2): (a1,b2,c3,b1,c2,b3), (a1,c2,b2,c1,b3,c3) and (a1,b1,c1).

Thus, the graph K1,3,3 admits a {C3p,C4q,C6r}-decomposition. ◻

Lemma 5. The graph K1,5,5 admits a {C3p,C4q,C6r}-decomposition.

Proof. The graph K1,5,5 has 35 edges for which the set of admissible triplets are given by (p,q,r){(5,5,0),(5,2,2),(3,5,1),(3,2,3),(1,8,0),(1,5,2),(1,2,4)}.

(5, 5, 0): (a1,b1,c1), (a1,b2,c2), (a1,b3,c3), (a1,b4,c4), (a1,b5,c5), (b1,c2,b3,c4), (b1,c3,b4,c5), (b2,c1,b3,c5), (b2,c3,b5,c4) and (b4,c1,b5,c2).

(5, 2, 2): (a1,b1,c1), (a1,b2,c2), (a1,b3,c3), (a1,b4,c4), (a1,b5,c5), (b2,c3,b5,c4), (b4,c1,b5,c2), (b1,c2,b3,c1,b2,c5) and (b1,c3,b4,c5,b3,c4).

(3, 5, 1): (a1,b1,c1), (a1,b4,c4), (a1,b5,c5), (b2,c3,b5,c4), (b4,c1,b5,c2), (a1,c2,b3,c3),
(b1,c3,b4,c5), (a1,b2,c5,b3) and (b1,c2,b2,c1,b3,c4).

(3, 2, 3): (a1,b1,c1), (a1,b4,c4), (a1,b5,c5), (b2,c3,b5,c4), (b4,c1,b5,c2), (a1,b2,c5,b4,c3,b3), (b1,c2,b2,c1,b3,c4) and (a1,c2,b3,c5,b1,c3).

(1, 8, 0): (a1,b1,c1), (a1,b2,c1,b3), (a1,b4,c5,b5), (b1,c2,b3,c4), (b2,c3,b3,c5), (b4,c4,b5,c1), (a1,c3,b1,c5), (a1,c2,b2,c4) and (b4,c2,b5,c3).

(1, 5, 2): (a1,b1,c1), (a1,b2,c1,b3), (a1,b4,c5,b5), (b1,c2,b3,c4), (b2,c3,b3,c5), (b4,c4,b5,c1), (b1,c3,b4,c2,a1,c5) and (b2,c2,b5,c3,a1,c4).

(1, 2, 4): (a1,b1,c1), (b1,c2,b3,c4), (b4,c4,b5,c1), (b1,c3,b4,c2,a1,c5), (b2,c2,b5,c3,a1,c4), (a1,b2,c1,b3,c5,b4) and (a1,b3,c3,b2,c5,b5).

Thus there exists a {C3p,C4q,C6r}-decomposition of the graph K1,5,5 for all admissible triplets (p,q,r)◻

Lemma 6. There exists a {C3p,C4q,C6r}-decomposition of K1,7,7.

Proof. In order to prove the existence of {C3p,C4q,C6r}-decomposition of K1,7,7 we consider the following admissible triplets:

(7, 0, 7): Seven 3-cycles are as follows: by (a1,b1,c1), (a1,b2,c2), (a1,b3,c3), (a1,b4,c4), (a1,b5,c5), (a1,b6,c6) and (a1,b7,c7). Seven 6-cycles are (b1,c2,b7,c6,b5,c3), (b1,c4,b5,c7,b2,c5), (b1,c7,b6,c1,b2,c6), (b3,c2,b6,c5,b4,c7), (b2,c3,b7,c5,b3,c4), (b3,c1,b5,c2,b4,c6) and (b4,c1,b7,c4,b6,c3).

(7, 3, 5): Seven 3-cycles are same as above. Required 4-cycles are (b3,c1,b5,c2), (b3,c6,b4,c7) and (b4,c2,b6,c5). Five edge disjoint 6-cycles are given by, (b1,c2,b7,c6,b5,c3), (b1,c4,b5,c7,b2,c5), (b1,c7,b6,c1,b2,c6), (b2,c3,b7,c5,b3,c4) and (b4,c1,b7,c4,b6,c3).

(7, 6, 3): The seven 3-cycles are as follows: (a1,b1,c1), (a1,b2,c2), (a1,b3,c3), (a1,b4,c4), (a1,b5,c5), (a1,b6,c6) and (a1,b7,c7). Six 4-cycles are (b3,c1,b5,c2), (b3,c6,b4,c7), (b4,c2,b6,c5), (b1,c4,b5,c7), (b1,c6,b2,c5) and (b2,c1,b6,c7). 6-cycles in the required decomposition are given by, (b1,c2,b7,c6,b5,c3), (b2,c3,b7,c5,b3,c4) and (b4,c1,b7,c4,b6,c3).

(7, 9, 1): (b3,c1,b5,c2), (b3,c6,b4,c7), (b4,c2,b6,c5), (b1,c4,b5,c7), (b1,c6,b2,c5), (b2,c1,b6,c7), (b3,c4,b7,c5), (b4,c1,b7,c3) and (b2,c3,b6,c4) are the nine 4-cycles and the required 6-cycle is given by (b1,c2,b7,c6,b5,c3). Required 3-cycles are same as above.

(5, 0, 8): (a1,b1,c1), (a1,b4,c4), (a1,b5,c5), (a1,b6,c6) and (a1,b7,c7) are the five copies of C3. Required 6-cycles are given by, (a1,c2,b7,c6,b5,c3), (a1,b2,c2,b1,c3,b3), (b1,c4,b5,c7,b2,c5), (b1,c7,b6,c1,b2,c6), (b3,c2,b6,c5,b4,c7), (b2,c3,b7,c5,b3,c4), (b3,c1,b5,c2,b4,c6) and (b4,c1,b7,c4,b6,c3).

(5, 3, 6): Three copies of 4-cycles are (b3,c1,b5,c6), (b4,c2,b7,c6) and (a1,c2,b5,c3). The six copies of C6 are (a1,b2,c2,b1,c3,b3), (b1,c4,b5,c7,b2,c5), (b1,c7,b6,c1,b2,c6), (b3,c2,b6,c5,b4,c7), (b2,c3,b7,c5,b3,c4) and (b4,c1,b7,c4,b6,c3). Five copies of 3-cycles are same as above.

(5, 6, 4): Five copies of 3-cycles are (a1,b1,c1), (a1,b4,c4), (a1,b5,c5), (a1,b6,c6) and (a1,b7,c7). Six copies of C4 are given by, (b3,c1,b5,c6), (b4,c2,b7,c6), (a1,c2,b5,c3), (a1,b2,c4,b3), (b1,c2,b2,c3) and (b3,c3,b7,c5). Four edge disjoint copies of 6-cycles are (b1,c4,b5,c7,b2,c5), (b1,c7,b6,c1,b2,c6), (b3,c2,b6,c5,b4,c7) and (b4,c1,b7,c4,b6,c3).

(5, 9, 2): Five copies of 3-cycles are same as above. Nine copies of 4-cycles are (b3,c1,b5,c6), (b4,c2,b7,c6), (a1,c2,b5,c3), (a1,b2,c4,b3), (b1,c2,b2,c3), (b3,c3,b7,c5), (b1,c4,b5,c7), (b1,c6,b2,c5) and (b2,c1,b6,c7). Two copies of 6-cycles are (b3,c2,b6,c5,b4,c7) and (b4,c1,b7,c4,b6,c3).

(5, 12, 0): (b3,c1,b5,c6), (b4,c2,b7,c6), (a1,c2,b5,c3), (a1,b2,c4,b3), (b1,c2,b2,c3), (b3,c3,b7,c5), (b1,c4,b5,c7), (b1,c5,b2,c6), (b2,c1,b4,c7), (b3,c2,b6,c7), (b6,c1,b7,c4) and (b4,c3,b6,c5) are the required 4-cycles. Five copies of 3-cycles are (a1,b1,c1), (a1,b4,c4), (a1,b5,c5), (a1,b6,c6) and (a1,b7,c7).

(3, 0, 9): Three copies of 3-cycles are (a1,b1,c1), (a1,b6,c6) and (a1,b7,c7). Nine edge disjoint copies of 6-cycles are given by, (a1,c2,b3,c1,b5,c3), (b3,c6,b5,c2,b6,c7), (b1,c5,b3,c3,b7,c6), (b2,c5,b7,c2,b4,c6), (a1,b2,c2,b1,c4,b3), (b1,c3,b2,c4,b5,c7), (b2,c1,b7,c4,b4,c7),
(a1,b4,c1,b6,c5,b5) and (a1,c4,b6,c3,b4,c5).

(3, 3, 7): Required copies of 3-cycles are same as above. Three copies of 4-cycles are (b3,c1,b5,c6), (b3,c2,b6,c7) and (a1,c2,b5,c3). 6-cycles in the required decomposition are (b1,c5,b3,c3,b7,c6), (b2,c5,b7,c2,b4,c6), (a1,b2,c2,b1,c4,b3), (b1,c3,b2,c4,b5,c7), (b2,c1,b7,c4,b4,c7), (a1,b4,c1,b6,c5,b5) and (a1,c4,b6,c3,b4,c5).

(3, 6, 5): (b3,c1,b5,c6), (b3,c2,b6,c7), (a1,c2,b5,c3), (b4,c2,b7,c6), (b1,c5,b2,c6) and (b3,c3,b7,c5) are the required copies of 4-cycles. Five copies of 6-cycles are given by, (a1,b2,c2,b1,c4,b3), (b1,c3,b2,c4,b5,c7), (b2,c1,b7,c4,b4,c7), (a1,b4,c1,b6,c5,b5) and (a1,c4,b6,c3,b4,c5). Two copies of 3-cycles in the required decomposition are (a1,b1,c1), (a1,b6,c6) and (a1,b7,c7).

(3, 9, 3): Three copies of 3-cycles are same as above. Nine edge disjoint copies of 4-cycles are given by (b3,c1,b5,c6), (b3,c2,b6,c7), (a1,c2,b5,c3), (b4,c2,b7,c6), (b1,c5,b2,c6), (b3,c3,b7,c5), (a1,b2,c4,b3), (b1,c2,b2,c3) and (b1,c4,b5,c7). Required copies of 6-cycles are (b2,c1,b7,c4,b4,c7), (a1,b4,c1,b6,c5,b5) and (a1,c4,b6,c3,b4,c5).

(3, 12, 1): Twelve edge disjoint copies of 4-cycles are (b3,c1,b5,c6), (b3,c2,b6,c7), (a1,c2,b5,c3), (b4,c2,b7,c6), (b1,c5,b2,c6), (b3,c3,b7,c5), (a1,b2,c4,b3), (b1,c2,b2,c3), (b1,c4,b5,c7), (b2,c1,b4,c7), (a1,c4,b4,c5) and (b6,c1,b7,c4). Required C6 is (a1,b4,c3,b6,c5,b5). Three copies of 3-cycles are (a1,b1,c1), (a1,b6,c6) and (a1,b7,c7).

(1, 0, 10): (a1,b1,c1) is the required C3. Ten edge disjoint copies of 6-cycles are (a1,c2,b3,c1,b5,c3), (b3,c6,b5,c2,b6,c7), (b1,c5,b3,c3,b7,c6), (b2,c5,b7,c2,b4,c6), (a1,b2,c2,b1,c4,b3), (b1,c3,b2,c4,b5,c7), (a1,c4,b4,c3,b6,c6), (a1,b4,c7,b2,c1,b6), (a1,c5,b6,c4,b7,c7) and (a1,b5,c5,b4,c1,b7).

(1, 3, 8): (b3,c1,b5,c6), (b3,c2,b6,c7) and (a1,c2,b5,c3) are the 3 edge disjoint copies of 4-cycles. Required 6-cycles are (b1,c5,b3,c3,b7,c6), (b2,c5,b7,c2,b4,c6), (a1,b2,c2,b1,c4,b3), (b1,c3,b2,c4,b5,c7), (a1,c4,b4,c3,b6,c6), (a1,b4,c7,b2,c1,b6), (a1,c5,b6,c4,b7,c7) and (a1,b5,c5,b4,c1,b7). The required C3 is (a1,b1,c1).

(1, 6, 6): One copy of C3 is given by, (a1,b1,c1). Required 4-cycles are as follows: (b3,c1,b5,c6), (b3,c2,b6,c7), (a1,c2,b5,c3), (b4,c2,b7,c6), (b1,c5,b2,c6) and (b3,c3,b7,c5). 6-cycles in the required decomposition are given by, (a1,b2,c2,b1,c4,b3), (b1,c3,b2,c4,b5,c7), (a1,c4,b4,c3,b6,c6), (a1,b4,c7,b2,c1,b6), (a1,c5,b6,c4,b7,c7) and (a1,b5,c5,b4,c1,b7).

(1, 9, 4): (a1,b1,c1) is the required C3. Nine copies of 4-cycles are as follows: (b3,c1,b5,c6), (b3,c2,b6,c7), (a1,c2,b5,c3), (b4,c2,b7,c6), (b1,c5,b2,c6), (b3,c3,b7,c5), (a1,b2,c4,b3), (b1,c2,b2,c3) and (b1,c4,b5,c7). Required 6-cycles are as follows: (a1,c4,b4,c3,b6,c6), (a1,b4,c7,b2,c1,b6), (a1,c5,b6,c4,b7,c7) and (a1,b5,c5,b4,c1,b7).

(1, 12, 2): (a1,b1,c1) is the required C3. Twelve copies of 4-cycles are as follows: (b3,c1,b5,c6), (b3,c2,b6,c7), (a1,c2,b5,c3), (b4,c2,b7,c6), (b1,c5,b2,c6), (b3,c3,b7,c5), (a1,b2,c4,b3),
(b1,c2,b2,c3), (b1,c4,b5,c7), (a1,c4,b7,c7), (a1,b4,c3,b6) and (a1,c5,b6,c6). 6-cycles in the required decomposition is given by, (b2,c1,b6,c4,b4,c7) and (a1,b5,c5,b4,c1,b7).

(1, 15, 0): Required 4-cycles are given by: (b3,c1,b5,c6), (b3,c2,b6,c7), (a1,c2,b5,c3), (b4,c2,b7,c6), (b1,c5,b2,c6), (b3,c3,b7,c5), (a1,b2,c4,b3), (b1,c2,b2,c3), (b1,c4,b5,c7), (a1,c5,b6,c6), (b4,c3,b6,c4), (a1,c4,b7,c7), (a1,b4,c5,b5), (a1,b6,c1,b7) and (b2,c1,b4,c7). The C3 in the required decomposition is (a1,b1,c1).

Thus the graph K1,7,7 admits a {C3p,C4q,C6r}-decomposition for all admissible triplets (p,q,r).  ◻

Theorem 4. The graph K1,m,m where m is odd, admits a {C3p,C4q,C6r}-decomposition where 1pm and 3p+4q+6r=m2+2m.

Proof. The graph K1,m,m has m2+2m edges. Since m is odd, here p0. Consider the case m1(mod 4). Let m=4n+1. Here,

K1,m,m=(a1,b1,c1)(K1,5,5C3)(K1,5,5C3)(K1,5,5C3)n copies(K4,4)(K4,4)(K4,4)n(n – 1) copies.

By Lemma 5, the graph K1,5,5C3 admits a (C3,C4,C6) decomposition for all admissible triplets. Theorem 2 guarantees the existence of (C4,C6)– cycle decomposition of K4,4 for all admissible pairs (q,r). Now consider the case m3(mod 4). Let m=4n+3. In this case,

K1,m,m=(a1,b1,c1)(K1,7,7C3)(K1,5,5C3)(K1,5,5C3)(K1,5,5C3)(n – 1)copies(K4,6)(K4,6)(K4,6)2(n – 1) copies.

By Lemmas 5 and 6, the graph K1,5,5C3 and K1,7,7C3 can be decomposed into copies of 3-cycles, 4-cycles and 6-cycles for all admissible triplets. Theorem 2 guarantees the existence of 4-cycles and 6-cycles for all possible pairs (q,r). Thus, the graph K1,m,m can be decomposed into {C3p,C4q,C6r} for all admissible triplets (p,q,r)◻

Lemma 7. There exists a {C3p,C4q,C6r}-decomposition of the graph K,,m.

Proof. The graph K,,m=K,,K2,m. By Theorem 3, the graph K,, admits a 3-cycle, 4-cycle and 6-cycle decomposition for all possible values of p, q and r. Theorem 2 guarantees the existence of 4-cycles and 6-cycles in K2,m for all possible pair (q,r).

It is easy to verify that whenever m=2 and p=2 then r=0. When p<2, then there exists 4-cycles and 6-cycles for all possible triplets (p,q,r).

Thus the graph K,,m can be decomposed into p copies of C3, q copies of C4 and r copies of C6 for all admissible triplets (p,q,r). ◻

Lemma 8. The graph K,m,m with m0(mod 4) has a {C3p,C4q,C6r}-decomposition.

Proof. Let {a1,a2,,al},{b1,b2,,bm} and {c1,c2,,cm} be the partite sets of K,m,m. In order to prove this lemma, consider a cyclic latin square of order m.

By Lemma 1, the edges corresponding to the entries in the first rows of the latin square corresponds to the maximum possible cycles of length 3. Thus p=m is achieved. Further, the entries in the first rows of the latin square can be then partitioned into 2×2 partial latin squares and the corresponding edges can be decomposed into copies of 3-cycles, 4-cycles and 6-cycles depending upon the values of (p,q,r) similar to Case 1 or Case 2 of Theorem 3, according as even or odd.

Next, we consider the remaining m rows of the latin square, where the entries will be of the form,

1 2 3 4 m1 m
+1 +2 +3 +4 1
+2 +3 +4 +5 +1
+3 +4 +5 +6 +1 +2
+4 +5 +6 +7 +2 +3

Note that each entry in the remaining m rows represent an edge between the second and third partite sets. We first decompose the edges corresponding to the entries in these m rows of the latin square into C4. Consider a block of first four rows, say rows +1,+2,+3,+4. The entries in the rows correspond to 4m edges and are decomposed into copies of C4 as follows: For example, we consider the bold entries as shown above, which corresponds to a 4-cycle (b1,c+1,bm1,c+2). Similarly, the underlined entries and the entries in the rectangular box corresponds to the 4-cycles (b1,c+3,b3,c+4) and (b2,c+2,bm,c+3), respectively. These three cycles of length four are taken together to have two copies of C6 and are given by (b1,c+1,bm1,c+2,bm,c+3) and (b1,c+2,b2,c+3,b3,c+4). Similarly, the remaining entries in this block can be decomposed into 4-cycles and 6-cycles accordingly. This can be repeated for all the block of four consecutive rows. After converting a group of 4-cycles into required number of 6-cycles, if there are unused 4-cycles in a block of four rows and if there are three such blocks, then it is straight forward to see that they can be transformed into 6-cycles using edge trading.

This proves the existence of {C3p,C4q,C6r}-decomposition of the graph K,m,m with m0(mod 4)◻

Lemma 9. For p=(+2) and 4q+6r=2(+2), the graph K,+2,+2 admits a {C3p,C4q,C6r}-decomposition.

Proof. Consider the bipartite graph K+2,+2, a proper subgraph of K,+2,+2. The degree of each vertex in K+2,+2 is +2. From this complete bipartite graph, we first construct a 2-factor F consisting q copies of C4 and r copies of C6. For this, we consider base cycles C=b1c1b2c2 and C=b2q+1c2q+1b2q+2c2q+2b2q+3c2q+3. Then the 2-factor F is given by {ρ0(C),ρ2(C),,ρ2q2(C)}{ρ0(C),ρ3(C),,ρ2q1(C)}. Now, if we decompose the graph (K,+2,+2F) into (+2) copies of 3-cycles, then we are done. This can be achieved as follows: after the removal of F and (+2) copies of 3-cycles from K,+2,+2, the edges in between second and third partite sets can be decomposed into 1-factors F1,F2,,F. Now, for 1i, the edges incident with a vertex ai together with a 1-factor Fi would yield a C3-factor, which completes the proof of this lemma. ◻

In order to prove the existence of {C3p,C4q,C6r}-decomposition of K,m,m with m2(mod4), we use a latin square which is constructed from an idempotent latin square. Since there is no idempotent latin square of order 2×2, we now prove the existence of {C3p,C4q,C6r}-decomposition of the graph K3,5,5.

Lemma 10. The graph K3,5,5 admits a {C3p,C4q,C6r}-decomposition.

Proof. In order to prove the existence of {C3p,C4q,C6r}-decomposition of K3,5,5 for all possible values of p,q and r, the following cases are considered.

(15, 1, 1): The maximum number of possible 3-cycles in the required decomposition of K3,5,5 is 15 which are as follows: (a1,b1,c3), (a1,b2,c4), (a1,b3,c1), (a1,b4,c5), (a1,b5,c2), (a2,b1,c5), (a2,b2,c3), (a2,b3,c4), (a2,b4,c2), (a2,b5,c1), (a3,b1,c4), (a3,b2,c5), (a3,b3,c2), (a3,b4,c1) and (a3,b5,c3). The remaining 10 edges from second and third partite which can be decomposed into a C4 and C6 given by, (b1,c2,b2,c1) and (b3,c3,b4,c4,b5,c5).

(13, 4, 0): Required edge disjoint copies of 3-cycles are (a1,b2,c4), (a1,b3,c1), (a1,b5,c2), (a2,b1,c5), (a2,b2,c3), (a2,b3,c4), (a2,b4,c2), (a2,b5,c1), (a3,b1,c4), (a3,b2,c5), (a3,b3,c2), (a3,b4,c1) and (a3,b5,c3). Four copies of 4-cycles are (b1,c1,b2,c2), (b4,c4,b5,c5), (a1,b1,c3,b4) and (a1,c3,b3,c5).

(13, 1, 2): Edge disjoint copies of 3-cycles are same as above. Required C4 is given by (b1,c1,b2,c2). Two copies of 6-cycles are (a1,b1,c3,b3,c5,b4) and (a1,c3,b4,c4,b5,c5).

(11, 4, 1): Required copies of 3-cycles are given by, (a1,b2,c4), (a1,b3,c1), (a1,b5,c2), (a2,b2,c3), (a2,b3,c4), (a2,b5,c1), (a3,b1,c4), (a3,b2,c5), (a3,b3,c2), (a3,b4,c1) and (a3,b5,c3). Four copies of 4-cycles are (a2,c2,b1,c5), (b4,c4,b5,c5), (a2,b1,c3,b4) and (a1,c3,b3,c5). Required C6 is (a1,b1,c1,b2,c2,b4).

(11, 1, 3): Required copies of 3-cycles will be the same as given above. Three copies of 6-cycles are (b3,c3,b4,c4,b5,c5), (a2,c2,b4,a1,b1,c5) and (a1,c3,b1,a2,b4,c5). Required C4 is (b1,c1,b2,c2).

(9, 7, 0): Seven copies of 4-cycles are as follows, (b1,c1,b2,c2), (a1,c3,b4,c5), (a1,b4,c2,b5), (a1,b1,a2,c2), (b1,c3,b3,c5), (a2,b3,c4,b4) and (a2,c4,b5,c5). Required copies of 3-cycles are given by (a1,b2,c4), (a1,b3,c1), (a2,b2,c3), (a2,b5,c1), (a3,b1,c4), (a3,b2,c5), (a3,b3,c2), (a3,b4,c1) and (a3,b5,c3).

(9, 4, 2): Nine copies of 3-cycles are given by (a1,b2,c4), (a1,b3,c1), (a2,b2,c3), (a2,b5,c1), (a3,b1,c4), (a3,b2,c5), (a3,b3,c2), (a3,b4,c1) and (a3,b5,c3). Four edge disjoint copies of 4-cycles are (b1,c1,b2,c2), (a1,c3,b4,c5), (a2,b3,c4,b4) and (b1,c3,b3,c5). Required 6-cycles are (a1,b1,a2,c4,b5,c2) and (a1,b4,c2,a2,c5,b5).

(9, 1, 4): Required copies of 3-cycles are same as given above. (b1,c1,b2,c2) is the required C4. Edge disjoint copies of 6-cycles are as follows: (a1,b1,a2,c4,b5,c2), (a1,b4,c2,a2,c5,b5), (a1,c3,b3,a2,b4,c5) and (b1,c3,b4,c4,b3,c5).

(7, 7, 1): (a1,b2,c4), (a1,b3,c1), (a2,b2,c3), (a2,b5,c1), (a3,b1,c4), (a3,b2,c5) and (a3,b4,c1) are the seven edge disjoint copies of 3-cycles and the required C6 is (a2,b3,c5,b1,c3,b4). Seven copies of 4-cycles are as follows: (b1,c1,b2,c2), (a1,b1,a2,c5), (a1,b4,c5,b5), (a2,c2,b4,c4), (a1,c2,b3,c3), (a3,c2,b5,c3) and (a3,b3,c4,b5).

(7, 4, 3): Four copies of 4-cycles are (b1,c1,b2,c2), (a1,b1,a2,c5), (a1,b4,c5,b5) and (a2,c2,b4,c4). Required 6-cycles are (a3,c2,b5,c4,b3,c3), (a1,c2,b3,a3,b5,c3) and (a2,b3,c5,b1,c3,b4). Seven copies of 3-cycles are same as given above.

(7, 1, 5): (a3,c2,b5,c4,b3,c3), (a1,c2,b3,a3,b5,c3), (a2,b3,c5,b1,c3,b4), (a1,b4,c2,a2,c5,b5) and (a1,b1,a2,c4,b4,c5) are the five edge disjoint copies of 6-cycles required and one copy of C4 is (b1,c1,b2,c2). Required seven copies of 3-cycles are (a1,b2,c4), (a1,b3,c1), (a2,b2,c3), (a2,b5,c1), (a3,b1,c4), (a3,b2,c5) and (a3,b4,c1).

(5, 10, 0): Five copies of 3-cycles are (a1,b2,c4), (a2,b2,c3), (a3,b1,c4), (a3,b2,c5) and (a3,b4,c1). Ten edge disjoint copies of 4-cycles are (b1,c3,b3,c5), (b3,c1,b5,c4), (a1,c2,a3,c3), (a2,b4,c3,b5), (a1,c1,a2,b3), (a3,b3,c2,b5), (a1,b4,c5,b5), (a1,b1,a2,c5), (a2,c2,b4,c4) and (b1,c1,b2,c2).

(5, 7, 2): Five copies of 3-cycles are same as given above. Required 4-cycle are as follows: (a1,b4,c5,b5), (a1,c2,a3,c3), (a2,b4,c3,b5), (b3,c1,b5,c4), (a2,c2,b4,c4), (a3,b3,c2,b5) and (b1,c1,b2,c2). 6-cycles in the required decomposition are given by (a1,b1,c3,b3,a2,c5) and (a1,b3,c5,b1,a2,c1).

(5, 4, 4): (a1,b2,c4), (a2,b2,c3), (a3,b1,c4), (a3,b2,c5) and (a3,b4,c1) are the five copies of 3-cycles. 4-cycles in the required decomposition are (a1,b4,c5,b5), (b3,c1,b5,c4), (a3,b3,c2,b5) and (b1,c1,b2,c2). Four copies of 6-cycles are given by, (a1,b1,c3,b3,a2,c5), (a1,b3,c5,b1,a2,c1), (a1,c2,b4,a2,b5,c3) and (a2,c2,a3,c3,b4,c4).

(5, 1, 6): Five copies of 3-cycles are same as given above. Six copies of 6-cycles are (a1,b1,c3,b3,a2,c5), (a1,b3,c5,b1,a2,c1), (a1,c2,b4,a2,b5,c3), (a2,c2,a3,c3,b4,c4), (a3,b3,c1,b1,c2,b5) and (b2,c1,b5,c4,b3,c2) and one copy of C4 in the required decomposition is (a1,b4,c5,b5).

(3, 1, 7): Edge disjoint copies of 3-cycles are (a3,b1,c4), (a3,b2,c5) and (a2,b2,c4). Required copies of 6-cycles are as follows: (a1,b1,c3,b3,a2,c5), (a1,b3,c5,b1,a2,c1), (a1,c2,b4,a2,b5,c3), (b2,c1,b5,c4,b3,c2), (a2,c2,a3,c1,b4,c3), (a3,b3,c1,b1,c2,b5) and (a1,b2,c3,a3,b4,c4). Required 4-cycle is given by (a1,b4,c5,b5).

(3, 4, 5): Edge disjoint copies of 3-cycles is same as given above. Required 4-cycles are (a1,b1,c3,b3), (a1,c1,a2,c5), (a2,b1,c5,b3) and (a1,b4,c5,b5). Five copies of 6-cycles are given by (a1,c2,b4,a2,b5,c3), (b2,c1,b5,c4,b3,c2), (a2,c2,a3,c1,b4,c3), (a3,b3,c1,b1,c2,b5) and (a1,b2,c3,a3,b4,c4).

(3, 7, 3): Seven copies of 4-cycles are (a1,b1,c3,b3), (a1,c1,a2,c5), (a2,b1,c5,b3), (a1,b4,c5,b5), (a1,c2,a2,c3), (a2,b4,c3,b5) and (a3,c1,b4,c2). Required 6-cycles are given by, (b2,c1,b5,c4,b3,c2), (a3,b3,c1,b1,c2,b5) and (a1,b2,c3,a3,b4,c4). Edge disjoint copies of 3-cycles are (a3,b1,c4), (a3,b2,c5) and (a2,b2,c4).

(3, 10, 1): (a1,b1,c3,b3), (a1,c1,a2,c5), (a2,b1,c5,b3), (a1,b4,c5,b5), (a1,c2,a2,c3), (a2,b4,c3,b5), (a3,c1,b4,c2), (b1,c1,b2,c2), (b3,c1,b5,c4) and (a3,b3,c2,b5) are the ten edge disjoint copies of 4-cycles. Required 6-cycle is given by (a1,b2,c3,a3,b4,c4). Edge disjoint copies of 3-cycles are same as given above.

(1, 10, 2): Ten copies of 4-cycles are (a1,b1,c3,b3), (a1,c1,a2,c5), (a2,b1,c5,b3), (a1,b4,c5,b5), (a3,b1,c4,b4), (a1,b2,a2,c4), (a3,c4,b2,c3), (b1,c1,b2,c2), (b3,c1,b5,c4) and (a3,b3,c2,b5). Two copies of 6-cycles are (a1,c2,b4,a2,b5,c3) and (a2,c2,a3,c1,b4,c3). Required C3 is (a3,b2,c5).

(1, 7, 4): Required copies of 4-cycles are as follows: (a1,b1,c3,b3), (a1,c1,a2,c5), (a2,b1,c5,b3), (a1,b4,c5,b5), (a3,b1,c4,b4), (a1,b2,a2,c4) and (a3,c4,b2,c3). Four copies of 6-cycles are (a1,c2,b4,a2,b5,c3), (a2,c2,a3,c1,b4,c3), (a3,b3,c1,b1,c2,b5) and (b2,c1,b5,c4,b3,c2). Required C3 is (a3,b2,c5).

(1, 4, 6): (a1,b4,c5,b5), (a3,b1,c4,b4), (a1,b2,a2,c4) and (a3,c4,b2,c3) gives the required 4-cycles. Edge disjoint copies of 6-cycles are given by (a1,c2,b4,a2,b5,c3), (a2,c2,a3,c1,b4,c3), (a3,b3,c1,b1,c2,b5), (b2,c1,b5,c4,b3,c2), (a1,b1,c3,b3,a2,c5) and (a1,c1,a2,b1,c5,b3). Required 3-cycle is (a3,b2,c5).

(1, 1, 8): (a1,c2,b4,a2,b5,c3), (a2,c2,a3,c1,b4,c3), (a3,b3,c1,b1,c2,b5), (b2,c1,b5,c4,b3,c2), (a1,b1,c3,b3,a2,c5), (a1,c1,a2,b1,c5,b3), (a1,b2,a2,c4,a3,b4) and (a1,c4,b1,a3,c5,b5) are the 8 edge disjoint copies of 6-cycles. Required 4-cycle is given by (b2,c4,b4,c5). One copy of C3 is given by (a3,b2,c5).

Thus the graph K3,5,5 admits a {C3p,C4q,C6r}-decomposition for all possible triplets. ◻

Definition 1. [17] In a n×n latin square, if each of the 2×2 subsquare has entries of the form,

x x+1
x+1 x

Next to prove the existence of {C3p,C4q,C6r}-decomposition of K,m,m with m2(mod 4), we use the following construction given by Elizabeth J. Billington [17].

Recall that if the cell (i,i) of a latin square of order n contains an entry i then the latin square is called idempotent latin square. When n is odd, an idempotent latin square can be constructed easily by using the entries in a cyclic order. But when n is even, an idempotent latin square can be constructed by using the stripping the transversal technique which is explained in [19].

Lemma 11. [17] For any P>2, there exists a latin square of order 2p+1 possessing p(p1)2×2 cell disjoint subsquares of the form (x).

In the following example, using an idempotent latin square of order 5, we construct an idempotent latin square of order 11 by using Lemma 11 which consists of 20 cell disjoint 2×2 subsquares of the form (x).

Example 1. Consider the latin square L5.

L5=

1 4 2 5 3
4 2 5 3 1
2 5 3 1 4
5 3 1 4 2
3 1 4 2 5

We can obtain the required latin square, L11 using Lemma 11 as given below.

L11=

0 2 1 4 3 6 5 8 7 10 9
2 1 0 7 8 3 4 9 10 5 6
1 0 2 8 7 4 3 10 9 6 5
4 7 8 3 0 9 10 5 6 1 2
3 8 7 0 4 10 9 6 5 2 1
6 3 4 9 10 5 0 1 2 7 8
5 4 3 10 9 0 6 2 1 8 7
8 9 10 5 6 1 2 7 0 3 4
7 10 9 6 5 2 1 0 8 4 3
10 5 6 1 2 7 8 3 4 9 0
9 6 5 2 1 8 7 4 3 0 10

Lemma 12. For m2(mod 4), there exists a {C3p,C4q,C6r}-decomposition of K,m,m.

Proof. The proof is splitted into 2 cases.

Case 1. is odd.

The graph K,m,m with m2(mod 4) has m2+2m edges. Let m=2M+1 and =2L+1. Here, the number of edges is odd and hence p0. Let us fix one C3 as (a0,b0,c0) in all possible decomposition. In order to prove this result, we use the latin square as described in Lemma 11, say Lm. This latin square is of order m, which will be of the form,

Clearly, pm and equality can be achieved by considering the entries in the first rows of Lm. These 3m edges can be decomposed into all possible 3, 4 and 6 cycles as follows:

It may be noted that the edges corresponding to the entry k in the cell (i,j) of the first rows correspond to a 3-cycle, (ai,bj,ck). Similarly, an entry c in the cell (a,b) after first rows correspond to a single edge from partite set 2 to partite set 3. Now, the entries in the first rows of the latin square Lm other than row 0 and column 0 can be partitioned into L(M1) 2×2 subsquares of the form (x) as given in Definition 1 together with L 2×2 partial latin square of the form:

2i1 2i
2i1 2i1 0
2i 0 2i

Observe that the edges corresponding to each of the 2×2 subsquares is isomorphic to K2,2,2 which admits a (C3,C4,C6)-decomposition by Lemma 2. Now consider each of the L partial latin squares

2i1 2i
2i1 2i1 0
2i 0 2i

together with the corresponding entries of row 0 and column 0, that is:

0 2i
0 2i1 2i
2i 2i1
2i1 2i 2i1 0
2i1 0 2i

The corresponding edges induce a graph isomorphic to K3,3,3C3. By Lemma 3, the graph K3,3,3C3 admits a (C3,C4,C6)-decomposition for all admissible triplets. Observe that the edges corresponding to the entries in the following cells are not used so far in the decomposition i=+1m{(0,i)}i=+1m{(i,0)}i=+1m{(i,1),(i,2),,(i,m)}.

Now consider the edges corresponding to the entries of the cells i=+1m{(0,i)}i=+1m{(i,0)}i=+1m{(i,i)}i=+1m{(i,i+1),(i+1,i)}.

That is, for some k with +1km, the entries will be of the form:

0 2k1 2k
Table 1 Partial Latin Square along with Row 0 and Column 0 Entries
0 2k1 2k
2k 2k1
2k 2k1 0
2k1 0 2k

The edges corresponding to the entries given in Table 1 can be either decomposed into three 4-cycles (a0,b2k1,c0,b2k), (a0,c2k1,b2k1,c2k) and (b0,c2k1,b2k,c2k) or into two 6-cycles (a0,c2k1,b2k1,c0,b2k,c2k) and (a0,b2k1,c2k,b0,c2k1,b2k).

The remaining edges, corresponding to the last (m) rows are decomposed into required (C4,C6) by grouping three 2×2 subsquares(note that each 2×2 subsquare corresponds to a 4-cycle) such that these subsquares are from 4 columns of Lm and contains four symbols. For example, see Tables 2 and 3.

1 M2 M1 2M1 2M
Table 2 Partial Latin Square 1
2 3 4
M1 2M1 2M
M2 2M 2M1
2M
2M1
1 2M5 2M4
Partial Latin Square 2
2 3 4
2M5 2M4
2M4 2M5
2M4 M4 M3
2M5 M3 M4

The edges corresponding to the entries as shown in Table 2 can be decomposed into two 6-cycles (b1,cM2,b2,c2M1,b3,c2M) and (b1,cM1,b2,c2M,b4,c2M1). Similarly, the edges corresponding to the entries in Table 3 can be decomposed into two 6-cycles (b1,c2M4,b3,cM3,b4,c2M5) and (b2,c2M4,b4,cM4,b3,c2M5).

Similarly, the edges corresponding to other groups with the above mentioned condition(4 column and 4 symbols) admits a (C4,C6)-decomposition for all admissible pairs.

Now it remains to show that when m2(mod4), the last m rows of Lm are partitioned into any of the form of Table 2 or 3. First, we consider M is odd. The case when m=2 has been dealt in Lemma 9. Consider m=6, by the construction of the latin square Lm, there are 3(M1) of 2×2 subsquares each of which corresponds to a 4-cycle. The entries in the last 6 rows of the latin square is grouped as shown in Figure 1(Note that a box in Figure 1 correspond to a subsquare in the latin square). Hence, we are done with m=6.

Next, the case m=10 is considered. By the construction of the latin square, there are 5(M1) subsquares and 5 partial latin square in the last 10 rows of the latin square. Note that, each subsquare corresponds to a 4-cycle. Thus, there are 5(M1) 4-cycles available corresponding to the entries in the last 10 rows. In order to construct 6-cycles, we may trade certain set of three 4-cycles for two 6-cycles. Here, depending upon m, the following 3 cases arise. when m1(mod6), then q1. Similarly, when m3(mod6), then q0 and when m5(mod6), then q1. For instance, consider the case m3(mod6). The entries in these 10 rows are grouped as shown in Figure 2. It is easy to verify that each of the partial latin square shown in Figure 2 either corresponds to three 4-cycles or two 6-cycles. Thus the edges corresponding to the entries in the last 10 rows of the latin square can be decomposed into (C4,C6) for all admissible pairs.

A similar approach can be used to partition the last 10 rows of Lm in the case m1(mod6) and m5(mod6). Thus, the case m=10 is done.

Next, we consider the case m=14. These 14 rows are made up of 7(M1) subsquares where each subsquare corresponds to a 4-cycle and 7 partial latin square. Depending upon the value of m, the following 3 cases arise. when m1(mod6), then q2. Similarly, when m3(mod6), then q0 and when m5(mod6), then q2. For instance, consider the case m3(mod6). The entries in these 14 rows can be partitioned into partial latin squares as shown in Figure 3.

Observe that each of the partial latin square considered in Figure 3 corresponds to either three 4-cycles or two 6-cycles. Thus the edges corresponding to the last 14 rows of the latin square can be decomposed into copies of (C4,C6) for all admissible pairs.

The same approach can be used to partition the last 14 rows of the latin square in cases when m1(mod6) and m5(mod6).

In the case when p=m, the edges corresponding to the last m rows can be decomposed into (C4,C6) using edge trading as follows. The edges corresponding to the entries in the subsquare corresponds to 4-cycles and by grouping three 4-cycles with the above mentioned condition(4 columns and 4 entries) can be decomposed into two 6-cycles. The partial latin square together with corresponding column 0 entry corresponds to a 6-cycle. For some k, this partial latin square will be of the form:

0 2k1 2k
2k1 2k 2k1 0
2k 2k1 0 2k

Two such 6-cycles can be decomposed into three 4-cycles as follows. For instance, consider m=6, then the last 6 rows of the latin square will be of the form; See Table 4.

Table 4 Last 6 Rows of m Rows
1 2 3 4 2M5 2M4 2M3 2M2 2M1 2M
2M4 M2 M1 2M1 2M 2M5 0 M4 M3 2M3 2M2
2M5 M1 M2 2M 2M1 0 2M4 M3 M4 2M2 2M3
2M2 2M1 2M 2M5 2M4 M4 M3 2M3 0 M2 M1
2M3 2M 2M1 2M4 2M5 M3 M4 0 2M2 M1 M2
2M5 2M4 M4 M3 2M3 2M2 M2 M1 2M1 0
2M4 2M5 M3 M4 2M2 2M3 M1 M2 0 2M

Consider the highlighted entries in the above Table 4 which correspond to three 4-cycles and two 6-cycles. There are 24 edges corresponding to the considered entries and can be decomposed into 6 copies of C4, given by, (b0,c2M5,b2M5,c2M3), (b2M2,c0,b2M5,c2M2), (b0,c2M4,b2M4,c2M2), (b2M4,cM4,b2M5,cM3), (b2M3,c0,b2M4,c2M3) and (b2M2,cM4,b2M3,cM3).

It is straightforward to check that similar edge trading is possible to have all possible (C4,C6) corresponding to the edges of the entries in these (m) rows.

When m>14, m=6x+10y+14z where x,y,z0 and the entries in the last m rows of the latin square can be partitioned as above and the corresponding edges can be decomposed into (C4,C6). Thus, there exists a {C3p,C4q,C6r}-decomposition of K,m,m with pm and m2(mod4) when M is odd.

Similarly, when M is even, the entries in the last m rows of the latin square can be grouped using the above mentioned conditions(4 columns and 4 entries).

Thus, there exists a {C3p,C4q,C6r}-decomposition of K,m,m with pm and m2(mod4).
Case 2. is even.

In order to prove this case, we consider a latin square of order m,

1 2 3 4 m1 m
2 1 4 3 m m1
1 +1 +2 2 3
1 +2 +1 3 2
+1 +2 +3 +4 1
+2 +1 +4 +3 1
+3 +4 +5 +6 +1 +2
+4 +3 +6 +5 +2 +1
m1 m 1 2 m3 m2
m m1 2 1 m2 m3

The first rows of the above latin square can be partitioned into 2×2 subsquares each of which correspond to K2,2,2. Lemma 2 guarantees the existence of 3,4 and 6 cycle decomposition of K2,2,2 for all admissible triplets. By the structure of the latin square, the edges corresponding to each 2×2 subsquare in the remaining (m) rows give rise to C4. As in previous case three 4 cycles can be used to construct two 6-cycles. Hence the proof of this lemma. ◻

Theorem 5. The graph K,m,n(mn), admits a {C3p,C4q,C6r}-decomposition.

Proof. The graph K,m,n=K,m,mK+m,nm. By Lemmas 8, 9, 10, 12, there exists a 3,4 and 6 cycle decomposition of K,m,m for all admissible triplets. Theorem 2 assures the existence of 4 and 6 cycle decomposition of K+m,nm for all m and n, where nm>2. Hence we consider the case nm=2 to complete the proof of this theorem.

Case 1. m0(mod4).

Consider the graph K,m,n with m0(mod4). In order to prove this result, it is enough to consider the graph K,+4,+6. The graph K,+4,+6 can be represented using a partial latin square of order +6, as shown in Figure 4.

<The first ×(+4) entries form a latin rectangle. Entries outside the latin rectangle are separated by double line. Each entry of column +5 and +6 denote an edge from partite set 1 to 3. Similarly, each entry of rows +1 to +6 denote an edge from partite set 2 to 3. That is, if the cell (,+5) contains the entry +5, then the corresponding edge is ac+5.</

The edges corresponding to the latin rectangle can be decomposed into cycles of length 3, 4 and 6 for all admissible triplets depending upon p, q and r similar to Case 1 or Case 2 of Theorem 3.

Now, we consider the edges corresponding to the entries outside the latin rectangle (the remaining edges from partite set 1 to 3 and the edges from partite set 2 and 3). We decompose these edges into C4 using two different construction which are as follows:

Construction 1. In this type of construction, we use the edges between partite set 1 to 3 and partite set 2 to 3 to construct a C4. For example, consider the four underlined entries as shown in table below. These entries correspond to a C4 namely (a1,c+5,b1,c+6) in K,+4,+6.

1 +5 +6
1 +5 +6
+5 +5
+6 +6

Construction 2. In this type of construction, we consider only the edges between the partite set 2 to 3 to construct a C4. For example, consider the four bold entries as shown in the table below. These entries also correspond to a C4 namely, (b1,c+3,b3,c+4).

1 3
+1 +3
+2 +4
+3 +3
+4 +4

Thus by using these two types of construction, all the remaining edges can be decomposed into 4-cycles. Thus, we have a C4-decomposition of the remaining edges.

In order to obtain all possible 4 and 6-cycles, we use two different types of edge trading, say, Type 1 and Type 2.
Type 1. This edge trading is similar to Construction 1, where we use edges between partite set 1 to 3 and partite set 2 to 3. For instance, consider the entries in rectangular box shown in Table 4. These entries correspond to three 4-cycles (a1,c+5,b1,c+6), (a2,c+6,b2,c1) and (b2,c+4,b4,c+5) which can be decomposed into two copies of C6 (a1,c+5,b4,c+4,b2,c+6) and (a2,c1,b2,c+5,b1,c+6).
Type 2. This edge trading is similar to Construction 2, where we use only the edges between partite set 2 to 3. For instance, consider the bold entries in Table 4. These entries correspond to three 4-cycles (b1,c+1,b+3,c+2), (b1,c+3,b3,c+4) and (b2,c+2,b+4,c+3) which can then be decomposed into 2 copies of C6 given by (b1,c+1,b+3,c+2,b+4,c+3) and (b1,c+2,b2,c+3,b3,c+4).

By using Type 1 and Type 2 edge trading, all the remaining edges can be decomposed into copies of (C4,C6).

Thus, all the remaining edges corresponding to the entries outside the latin rectangle can be decomposed into copies of 4 and 6 cycles.

Thus the graph K,m,n with m0(mod4) admits a {C3p,C4q,C6r}-decomposition.

m=2(mod4).

In this case, let K,m,m+2=K,m,mK+m,2. By Theorem 2, all the edges corresponding to K+m,2 can be decomposed into edge disjoint copies of C4. In order to obtain cycles of length 6, we use edge trading. Let be even. In order to prove this result, it is enough to consider the graph K,+2,+4. Then the graph K,+2,+2 along with the entries corresponding to the bipartite graph K2+2,2 can be represented using the partial latin square of order +4. See Figure 5.

Similar to Case 1, the first ×(+2) entries form a latin rectangle. Entries outside the latin rectangle are separated by double line. Each entry outside the latin rectangle represent a single edge. The edges corresponding to the entries in the latin rectangle can be decomposed into copies of 3-cycles, 4-cycles and 6-cycles similar to Case 1 of Theorem 3.

By the structure of the latin square, the edges corresponding to the entries in rows +1 and +2 can be decomposed into 4-cycles. Now in order to obtain all possible 4 and 6-cycles, we use the following edge trading.

Here, we take +22 C4 from K,+2,+2(the edges corresponding to the entries in the last 2 rows of the latin square K,+2,+2) together with the edges of K2+2,2 which can be then decomposed into 6-cycles. For instance, consider the highlighted entries in Table 5. The edges corresponding to these entries gives rise to a C6 given by (b1,c+1,b2,c+3,a1,c+4). Similarly, the entries in the rectangular box correspond to a C6 given by (b1,c+2,b2,c+4,a2,c+3). By proceeding this way, the remaining edges can be decomposed into copies of C6.

When is odd, the complete tripartite graph K,m,n can be represented using a partial latin square similar to the even case where the edges corresponding to the entries in the latin rectangle can be decomposed into 3, 4 and 6 cycles similar to Case 2 of Theorem 3. The remaining edges corresponding to the entries outside the latin rectangle can be decomposed into 4 and 6 cycles using the above edge trading technique.

Thus the graph K,m,n(mn) can be decomposed into p copies of C3, q copies of C4 and r copies of C6 for all admissible triplets (p,q,r). ◻

Theorem 1. The complete tripartite graph K,m,n(mn) admits a {C3p,C4q,C6r}-decomposition if and only if the partite sets are of same parity and 3p+4q+6r=m+mn+n.

Proof. The proof follows from Lemma 7, Theorem 3, Theorem 4 and Theorem 5. ◻

4. Conclusion

In this paper, the necessary condition for the existence of {C3p,C4q,C6r}-decomposition of complete tripartite graph K,m,n(mn) has been proved to be sufficient. This answers the problem posted by Billington in the affirmative. The problem of {C3p,C4q,C6r}-decomposition of KmKn¯ is still open for m>3.

Declaration of Competing Interest

There is no conflict of interest related to this work.

References:

  1. Balakrishnan, R. and Ranganathan, K., 2012. A Textbook of Graph Theory. Springer Science and Business Media.
  2. West, D. B., 2001. Introduction to Graph Theory. Prentice Hall.
  3. Ganesamurthy, S. and Paulraja, P., 2019. Decompositions of complete tripartite graphs into cycles of lengths 3 and 6. Australasian Journal of Combinatorics, 73(1), pp.220-241.
  4. Cavenagh, N. J. and Billington, E. J., 2000. On decomposing complete tripartite graphs into 5-cycles. Australasian Journal of Combinatorics, 22, pp.41-62.
  5. Bryant, D., 2007. Cycle decompositions of complete graphs. In London Mathematical Society Lecture Note Series (Vol. 346, pp.67-97).
  6. Paulraja, P. and Srimathi, R., 2020. Decompositions of complete equipartite graphs into cycles of lengths 3 and 6. Australasian Journal of Combinatorics, 78(2), pp.297-313.
  7. Paulraja, P. and Srimathi, R., 2021. Decomposition of the tensor product of complete graphs into cycles of lengths 3 and 6. Discussiones Mathematicae Graph Theory, 41(1), pp.249-266.
  8. Ganesamurthy, S. and Paulraja, P., 2021. Decompositions of some classes of dense graphs into cycles of lengths 4 and 8. Graphs and Combinatorics, 37(4), pp.1291-1310.
  9. Ezhilarasi, A.P. and Muthusamy, A., 2023. Decomposition of complete equipartite graphs into paths and cycles of length 2p. Discrete Mathematics, 346(1), p.113160.
  10. Alipour, S., Mahmoodian, E. S. and Mollaahmadi, E., 2012. On decomposing complete tripartite graphs into 5-cycles. Australasian Journal of Combinatorics, 54, pp.289-301.
  11. Billington, E. J. and Hoffman, D. G., 2003. Decomposition of complete tripartite graphs into gregarious 4-cycles. Discrete Mathematics, 261(1-3), pp.87-111.

  12. Billington, E. J. and Cavenagh, N. J., 2007. Decomposing complete tripartite graphs into closed trails of arbitrary lengths. Czechoslovak Mathematical Journal, 57(132), pp.523-551.

  13. Billington, E. J. and Cavenagh, N. J., 2011. Decomposing complete tripartite graphs into 5-cycles when the partite sets have similar size. Aequationes Mathematicae, 82(3), pp.277-289.

  14. Cavenagh, N. J., 1998. Decompositions of complete tripartite graphs into k-cycles. Australasian Journal of Combinatorics, 18, pp.193-200.

  15. Cavenagh, N. J., 2002. Further decompositions of complete tripartite graphs into 5-cycles. Discrete Mathematics, 256(1-2), pp.55-81.
  16. Mahmoodian, E. S. and Mirzakhani, M., 1995. Decomposition of complete tripartite graphs into 5-cycles. In Combinatorics Advances (pp. 235-241).
  17. Billington, E. J., 1999. Decomposing complete tripartite graphs into cycles of lengths 3 and 4. Discrete Mathematics, 197/198, pp.123-135.

  18. Chou, C.-C., Fu, C.-M. and Huang, W.-C., 1999. Decomposition of Km,n into short cycles. Discrete Mathematics, 197, pp.195-203.

  19. Lindner, C. C. and Rodger, C. A., 2017. Design Theory. CRC Press.