Menu
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 \( \{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\} \)-decomposition. In this paper, the necessary conditions for the existence of \( \{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\} \)-decomposition of \( K_{\ell, m, n}(\ell \leq m \leq n) \) 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)}.
All graphs considered here are simple, finite and undirected. Let \(K_{m}\) and \(C_{m}\) denote the complete graph and a cycle on \(m\) vertices. Let \(P_{m + 1}\) denotes a path on \(m\) edges. If \(H_{1}, H_{2}, …, H_{n}\) are edge disjoint subgraphs of \(G\) such that \(E(G) = E(H_{1}) \cup E(H_{2}) \cup … \cup E(H_{n})\), where \(\cup\) denotes the disjoint union of graphs, then we say that \(H_{1}, H_{2}, …, H_{n}\) decomposes \(G\). If each \(H_{i} \simeq H\), then we say that \(H\) decomposes \(G\) and it is denoted by \(H|G\). If each \(H\) is a cycle \(C_{m}\), then we say that \(G\) admits a \(C_{m}\)-decomposition or \(m\)-cycle decomposition and is denoted by \(C_{m}|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^{\prime}, q^{\prime}, r^{\prime})\) is said to be an admissible triplet for the sub-graph \(H\), if \(3p^{\prime} + 4q^{\prime} + 6r^{\prime} = |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 \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition. For terms not defined here one can refer to [1,2].
A latin square of order \(n\) is a \(n \times 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, 1 \leq i \leq n\). A latin square of order \(n\) is said to be cyclic if it’s first row entries are \(a_{1}, a_{2}, \cdots, a_{n}\), then the \(p^{th}\) row entries are \(a_{p}, a_{p+1}, a_{p+2}, \cdots, a_{p-1}\) 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 \(\ell \times 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 \(\{C_{3}^{p}, C_{6}^{r}\}\)-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 \(\{C_{4}^{p}, C_{8}^{q}\}\)-decomposition. Very recently, Ezhilarasi and Muthusamy [9], proved the necessary and sufficient conditions for the existence of \(\{P_{2p+1}, C_{2p}\}\)-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 \(\{C_{3}^{p}, C_{4}^{q}\}\)-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 \(\{C_{3}^{p}, C_{6}^{r}\}\)-decomposition of complete tripartite graphs. Billington suggested finding the necessary and sufficient conditions for the existence of \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of \(K_{\ell, m, n}(\ell \leq m \leq n)\). The main theorem of this paper answer this question in the affirmative.
Theorem 1. The complete tripartite graph \(K_{\ell, m, n}(\ell \leq m \leq n)\) admits a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition if and only if the partite sets are of same parity and \(3p + 4q + 6r = \ell m + mn + \ell 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_{\ell, \, m, \, n}(\ell \leq m \leq n)\) has an edge disjoint decomposition into \(p\) cycles of length 3 and \(q\) cycles of length 4 if and only if,
\(\ell, m, n\) are all even or odd.
If \(\ell\) is even or if \(\ell\) is odd and \(m – \ell \equiv 0(\)mod\(\ 4)\), then \(p \leq \ell m\).
If \(\ell\) is odd and \(m – \ell \equiv 2(\)mod\(\ 4)\), then \(p \leq \ell m – 2\).
The value of \(p\) decreases from its maximum value in steps of size 4, down to 0 if \(\ell\) is even and to 1, if \(\ell\) is odd.
If we put \(q = 0\) in Theorem 1, we have the following
Corollary 2. Let \(K_{\ell, m, n}(\ell \leq m \leq n)\) be the complete tripartite. Then this complete tripartite graph admits a \(\{C_{3}^{p}, C_{6}^{r}\}\)-decomposition whenever the partite sets are of same parity and \(3p + 6r = \ell m + mn + \ell n\).
The corollary 2 subsumes the main result of [3].
Corollary 3. [3] Let \(K_{\ell, m, n}(\ell \leq m \leq n)\) be the complete tripartite graph and let \(K_{\ell, m, n} \neq K_{1, 1, n}\) when \(n \equiv 1(mod \,\, 6)\) and \(n > 1\). If \(\ell \equiv m \equiv n (mod \,\, 6)\), then \(K_{\ell, m, n}\) admits a \(\{C_{3}^{p}, C_{6}^{r}\}\)-decomposition for any \(p \equiv \ell (mod \,\, 2)\), with \(0 \leq p \leq \ell m\).
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 \(K_{2m, 2n}\) and \(K_{2n + 1, 2n + 1} – F\) admits a \(\{C_{4}^{p}, C_{6}^{q}, C_{8}^{r}\}\) – decomposition whenever \(4p + 6q + 8r = |E(K_{2m, 2n})|\) or \(4p + 6q + 8r = |E(K_{2n + 1, 2n + 1} – F)|\), where \(F\) is a \(1\)-factor of \(K_{2n + 1, 2n + 1}\).
Lemma 1. [4] Let \(\ell, m\) and \(n\) be integers such that \(\ell \leq m \leq n\). A latin rectangle of order \(\ell \times m\) based on \(n\) elements is equivalent to the existence of \(\ell m\) edge-disjoint triangles sitting inside the complete tripartite graph \(K_{\ell, m, n}\).
Remark 1. Since a cycle of length 3 in a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of \(K_{\ell, m, n}(\ell \leq m \leq n)\) needs to visit all three partite sets, in any \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of \(K_{\ell, m, n}\), maximum number of \(3\)-cycles is \(\ell m\).
Throughout this paper, we denote \(V(K_{\ell, m, n}) = A \cup B \cup C\) where \(A = \{a_{1}, a_{2}, …, a_{\ell}\}\), \(B = \{b_{1}, b_{2}, …, b_{m}\}\) and \(C = \{c_{1}, c_{2}, …, c_{n}\}\).
In this section, we prove the necessary conditions for the existence
of \(\{C_{3}^{p}, C_{4}^{q},
C_{6}^{r}\}\)–
decomposition of the complete tripartite graphs \(K_{\ell, m, n}\) are sufficient whenever
\(\ell = m = n\).
Remark 2. [17] A \(C_{3}\)-decomposition of the complete tripartite graph \(K_{m, m, m}\) can be achieved using a latin square as follows: an entry \(k\) in the cell \((i, j)\) corresponds to a \(C_{3}\), given by \((a_{i}, b_{j}, c_{k})\) .
Lemma 2. The graph \(K_{2, 2, 2}\) admits a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition.
Proof. In this case, all the possible triplets are: \((p, q, r) \in \{(4, 0, 0), (0, 3, 0), (0, 0, 2), (2, 0, 1)\}\). The decomposition is given below.
(4, 0, 0): \((a_{1}, b_{1}, c_{2})\), \((a_{1}, b_{2}, c_{1})\), \((a_{2}, b_{1}, c_{1})\) and \((a_{2}, b_{2}, c_{2})\).
(0, 3, 0): \((a_{1}, b_{2}, a_{2}, b_{1})\), \((b_{1},c_{2}, b_{2}, c_{1})\) and \((a_{1}, c_{2}, a_{2}, c_{1})\).
(0, 0, 2): \((a_{1}, b_{1}, c_{1}, b_{2}, a_{2}, c_{2})\) and \((a_{1}, b_{2}, c_{2}, b_{1}, a_{2}, c_{1})\).
(2, 0, 1):\((a_{1}, b_{1}, c_{1})\), \((a_{2}, b_{2}, c_{2})\) and \((a_{1}, b_{2}, c_{1}, a_{2}, b_{1}, c_{2})\).
Thus, the graph \(K_{2, 2, 2}\) admits a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition. ◻
Lemma 3. The graph \(K_{3, 3, 3}\) admits a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition.
Proof. Consider a cyclic idempotent latin square of order 3. By Remark 2, every entry \(k\) in the latin square corresponds to a \(C_{3}\) in \(K_{3, 3, 3}\). For a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of \(K_{3, 3, 3}\), it is obvious that \(p \neq 0\), since the total number of edges is odd. We fix a \(C_{3}\) namely \((a_{1}, b_{1}, c_{1})\), in all possible decompositions given below:
Now, \((p, q, r) \in \{(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): \((a_{1}, b_{1}, c_{1}), (a_{2}, b_{2}, c_{3}), (a_{1}, b_{3}, c_{2}), (a_{2}, b_{3}, c_{1}), (a_{3}, b_{1}, c_{2}), (a_{3}, b_{2}, c_{1})\), \((a_{3}, b_{3}, c_{3})\) and \((a_{1}, b_{2}, c_{2}, a_{2}, b_{1}, c_{3})\).
(5, 0, 2): \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{2}, c_{2})\), \((a_{2}, b_{2}, c_{3})\), \((a_{2}, b_{1}, c_{2})\), \((a_{3}, b_{3}, c_{2})\), \((a_{1}, b_{3}, a_{2}, c_{1}, a_{3}, c_{3})\) and \((a_{3}, b_{1}, c_{3}, b_{3}, c_{1}, b_{2})\).
(5, 3, 0): \((a_{1}, b_{1}, c_{1})\), \((a_{2}, b_{3}, c_{1})\), \((a_{3}, b_{1}, c_{2})\), \((a_{3}, b_{2}, c_{1})\), \((a_{3}, b_{3}, c_{3})\), \((a_{1}, b_{2}, c_{2}, b_{3})\), \((a_{1}, c_{2}, a_{2}, c_{3})\) and \((a_{2}, b_{1}, c_{3}, b_{2})\).
(3, 3, 1): \((a_{1}, b_{1}, c_{1})\), \((a_{2}, b_{1}, c_{3})\), \((a_{3}, b_{1}, c_{2})\), \((a_{1}, b_{2}, c_{1}, b_{3})\), \((a_{2}, b_{2}, c_{2}, b_{3})\), \((a_{3}, b_{3}, c_{3}, b_{2})\) and \((a_{1}, c_{2}, a_{2}, c_{1}, a_{3}, c_{3})\).
(3, 0, 3): \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{2}, c_{3})\), \((a_{1}, b_{3}, c_{2})\), \((a_{2}, b_{1}, c_{3}, a_{3}, b_{2}, c_{1})\), \((a_{2}, b_{3}, c_{1}, a_{3}, b_{1}, c_{2})\) and \((a_{2}, b_{2}, c_{2}, a_{3}, b_{3}, c_{3})\).
(1, 3, 2): \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{2}, a_{2}, b_{3})\), \((a_{1}, c_{2}, b_{2}, c_{3})\), \((a_{2}, c_{1}, a_{3}, c_{3})\), \((a_{2}, b_{1}, c_{3}, b_{3}, a_{3}, c_{2})\) and \((a_{3}, b_{1}, c_{2}, b_{3}, c_{1}, b_{2})\).
(1, 6, 0): \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{2}, a_{2}, b_{3})\), \((a_{1}, c_{2}, b_{2}, c_{3})\), \((a_{2}, c_{1}, a_{3}, c_{3})\), \((a_{3}, b_{2}, c_{1}, b_{3})\), \((a_{2}, b_{1}, a_{3}, c_{2})\) and \((b_{1}, c_{2}, b_{3}, c_{3})\).
(1, 0, 4): \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{2}, a_{2}, c_{1}, a_{3}, c_{3})\), \((a_{1}, b_{3}, a_{2}, c_{3}, b_{2}, c_{2})\), \((a_{2}, b_{1}, c_{3}, b_{3}, a_{3}, c_{2})\) and \((a_{3}, b_{1}, c_{2}, b_{3}, c_{1}, b_{2})\).
The above cases guarantees the existence of \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of \(K_{3, 3, 3}\) for all admissible triplets. ◻
Theorem 3. The graph \(K_{\ell, \ell, \ell}\), admits a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition.
Proof. Let the partite sets of \(K_{\ell, \ell, \ell}\) be \(A \cup B \cup C\) where, \(A = \{a_{1}, a_{2}, …, a_{\ell}\}\), \(B = \{b_{1}, b_{2}, …, b_{\ell}\}\) and \(\{c_{1}, c_{2}, …, c_{\ell}\}\). We consider the following two cases.
Case 1. \(\ell\) is even.
Consider a cyclic latin square of order \(\ell\). This latin square is partitioned into \(2 \times 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) \in \{(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 \((a_{i}, b_{j}, c_{k + 1})\) and \((a_{i + 1}, b_{j + 1}, c_{k + 2})\). The required \(6\)-cycle is \((a_{i}, c_{k}, b_{j}, a_{i + 1}, c_{k + 1}, b_{j + 1})\).
(0, 3, 0): The required \(4\)-cycles are given by \((a_{i}, c_{k}, b_{j}, c_{k + 1})\), \((a_{i}, b_{j}, a_{i + 1}, b_{j + 1})\) and \((a_{i + 1}, c_{k + 1}, b_{j + 1}, c_{k + 2})\).
(0, 0, 2): \((a_{i}, c_{k}, b_{j}, c_{k + 1}, a_{i + 1}, b_{j + 1})\) and \((a_{i}, c_{k + 1}, b_{j + 1}, c_{k + 2}, a_{i + 1}, b_{j})\) are the required \(6\)-cycles.
Thus each of these \(2 \times 2\) partial latin squares can be decomposed into \(3\), \(4\) and \(6\) cycles for all admissible triplets.
Hence \(K_{\ell, \ell, \ell}\),
where \(\ell\) is even, admits a \(\{C_{3}^{p}, C_{4}^{q},
C_{6}^{r}\}\)-decomposition.
Case 2. \(\ell\) is
odd.
Consider a cyclic latin square of order \(\ell\). As \(\ell\) is odd, \(p \neq 0\). Hence, we fix a \(3\)-cycle, \((a_{1}, b_{1}, c_{1})\) that will be present in all possible decompositions. For \(1 \leq i \leq \frac{\ell – 1}{2}\), with the first row and first column entries of this latin square, we first partitioned the \(2 \times 2\) partial latin square entries of the form,
| \(1\) | \( 2i \) | \( 2i + 1 \) | |
| \(1\) | \(2i\) | \(2i + 1\) | |
| \(2i\) | \(2i\) | \( 4i – 1 \) | \( 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) \in \{(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): \((a_{1}, b_{2i}, c_{2i})\), \((a_{1}, b_{2i + 1}, c_{2i + 1})\), \((a_{2i}, b_{1}, c_{2i})\), \((a_{2i + 1}, b_{1}, c_{2i + 1})\), \((a_{2i}, b_{2i}, c_{4i})\), \((a_{2i + 1}, b_{2i + 1}, c_{4i + 1})\) and \((a_{2i}, c_{4i – 1}, b_{2i}, a_{2i + 1}, c_{4i}, b_{2i + 1})\).
(4, 3, 0): \((a_{1}, b_{2i}, c_{2i})\), \((a_{1}, b_{2i + 1}, c_{2i + 1})\), \((a_{2i}, b_{1}, c_{2i})\), \((a_{2i + 1}, b_{1}, c_{2i + 1})\), \((a_{2i}, c_{4i – 1}, b_{2i}, c_{4i})\), \((a_{2i}, b_{2i}, a_{2i + 1}, b_{2i + 1})\) and \((a_{2i + 1}, c_{4i}, b_{2i + 1}, c_{4i + 1})\).
(4, 0, 2): \((a_{1}, b_{2i}, c_{2i})\), \((a_{1}, b_{2i + 1}, c_{2i + 1})\), \((a_{2i}, b_{1}, c_{2i})\), \((a_{2i + 1}, b_{1}, c_{2i + 1})\), \((a_{2i}, c_{4i – 1}, b_{2i}, c_{4i}, a_{2i + 1}, b_{2i + 1})\) and \((a_{2i}, c_{4i}, b_{2i + 1}, c_{4i + 1}, a_{2i + 1}, b_{2i})\).
(2, 3, 1): \((a_{2i}, b_{2i}, c_{2i})\), \((a_{2i + 1}, b_{2i + 1}, c_{2i})\), \((a_{1}, b_{2i}, c_{4i}, b_{2i + 1})\), \((a_{1}, c_{2i}, b_{1}, c_{2i + 1})\), \((a_{2i}, b_{1}, a_{2i + 1}, c_{4i})\) and \((a_{2i}, b_{2i + 1}, c_{4i + 1}, a_{2i + 1}, b_{2i}, c_{4i – 1})\).
(2, 0, 3): \((a_{2i}, b_{2i}, c_{4i})\), \((a_{2i + 1}, b_{2i + 1}, c_{4i + 1})\), \((a_{2i}, c_{4i – 1}, b_{2i}, a_{2i + 1}, c_{4i}, b_{2i + 1})\), \((a_{1}, b_{2i}, c_{2i}, a_{2i}, b_{1}, c_{2i + 1})\) and \((a_{1}, b_{2i + 1}, c_{2i + 1}, a_{2i + 1}, b_{1}, c_{2i})\).
(0, 6, 0): \((a_{1}, b_{2i}, a_{2i}, b_{2i + 1})\), \((a_{2i}, b_{1}, a_{2i + 1}, c_{4i})\), \((a_{2i}, c_{2i}, b_{2i}, c_{2i + 1})\), \((a_{2i + 1}, b_{2i}, c_{4i}, b_{2i + 1})\), \((a_{1}, c_{2i}, b_{1}, c_{2i + 1})\) and \((a_{2i + 1}, c_{4i + 1}, b_{2i + 1}, c_{2i + 1})\).
(0, 0, 4): \((a_{1}, b_{2i + 1}, c_{2i + 1}, a_{2i + 1}, b_{2i}, c_{2i})\), \((a_{1}, b_{2i}, a_{2i}, c_{2i}, b_{1}, c_{2i + 1})\), \((a_{2i}, b_{1}, a_{2i + 1}, c_{4i + 1}, b_{2i + 1}, c_{4i})\) and \((a_{2i}, b_{2i + 1}, a_{2i + 1}, c_{4i}, b_{2i}, c_{4i – 1})\).
(0, 3, 2): \((a_{2i}, b_{2i}, a_{2i + 1}, b_{2i + 1})\), \((a_{2i}, c_{4i – 1}, b_{2i}, c_{4i})\), \((a_{2i + 1}, c_{4i}, b_{2i + 1}, c_{4i + 1})\), \((a_{1}, b_{2i}, c_{2i}, a_{2i}, b_{1}, c_{2i + 1})\) and \((a_{1}, b_{2i + 1}, c_{2i + 1}, a_{2i + 1}, b_{1}, c_{2i})\).
The remaining entries of the latin square can be partitioned into \(2 \times 2\) partial latin squares where the edges corresponding to each of the \(2 \times 2\) partial latin square can be decomposed into all possible \((C_{3}, C_{4}, C_{6})\) as in Case 1.
Hence for all admissible triplets \((p, q, r)\), the graph \(K_{\ell, \ell, \ell}\) admits a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition. ◻
In this section, we have proved the necessary conditions for the existence of \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of the complete tripartite graphs \(K_{\ell, m, n}(\ell \leq m \leq n)\) are sufficient.
Lemma 4. The graph \(K_{1, 3, 3}\) admits a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition.
Proof. The graph \(K_{1, 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) \in \{(3, 0, 1), (1, 3, 0), (1, 0, 2)\}\).
(3, 0, 1): \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{2}, c_{2})\), \((a_{1}, b_{3}, c_{3})\) and \((b_{1}, c_{2}, b_{3}, c_{1}, b_{2}, c_{3})\).
(1, 3, 0): \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{2}, c_{1}, b_{3})\), \((a_{1}, c_{2}, b_{2}, c_{3})\) and \((b_{1}, c_{2}, b_{3}, c_{3})\).
(1, 0, 2): \((a_{1}, b_{2}, c_{3}, b_{1}, c_{2}, b_{3})\), \((a_{1}, c_{2}, b_{2}, c_{1}, b_{3}, c_{3})\) and \((a_{1}, b_{1}, c_{1})\).
Thus, the graph \(K_{1, 3, 3}\) admits a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition. ◻
Lemma 5. The graph \(K_{1, 5, 5}\) admits a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition.
Proof. The graph \(K_{1, 5, 5}\) has 35 edges for which the set of admissible triplets are given by \((p, q, r) \in \{(5, 5, 0), (5, 2, 2), (3, 5, 1), (3, 2, 3), (1, 8, 0), (1, 5, 2), (1, 2, 4)\}\).
(5, 5, 0): \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{2}, c_{2})\), \((a_{1}, b_{3}, c_{3})\), \((a_{1}, b_{4}, c_{4})\), \((a_{1}, b_{5}, c_{5})\), \((b_{1}, c_{2}, b_{3}, c_{4})\), \((b_{1}, c_{3}, b_{4}, c_{5})\), \((b_{2}, c_{1}, b_{3}, c_{5})\), \((b_{2}, c_{3}, b_{5}, c_{4})\) and \((b_{4}, c_{1}, b_{5}, c_{2})\).
(5, 2, 2): \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{2}, c_{2})\), \((a_{1}, b_{3}, c_{3})\), \((a_{1}, b_{4}, c_{4})\), \((a_{1}, b_{5}, c_{5})\), \((b_{2}, c_{3}, b_{5}, c_{4})\), \((b_{4}, c_{1}, b_{5}, c_{2})\), \((b_{1}, c_{2}, b_{3}, c_{1}, b_{2}, c_{5})\) and \((b_{1}, c_{3}, b_{4}, c_{5}, b_{3}, c_{4})\).
(3, 5, 1): \((a_{1},
b_{1}, c_{1})\), \((a_{1}, b_{4},
c_{4})\), \((a_{1}, b_{5},
c_{5})\), \((b_{2}, c_{3}, b_{5},
c_{4})\), \((b_{4}, c_{1}, b_{5},
c_{2})\), \((a_{1}, c_{2}, b_{3},
c_{3})\),
\((b_{1}, c_{3}, b_{4}, c_{5})\), \((a_{1}, b_{2}, c_{5}, b_{3})\) and \((b_{1}, c_{2}, b_{2}, c_{1}, b_{3},
c_{4})\).
(3, 2, 3): \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{4}, c_{4})\), \((a_{1}, b_{5}, c_{5})\), \((b_{2}, c_{3}, b_{5}, c_{4})\), \((b_{4}, c_{1}, b_{5}, c_{2})\), \((a_{1}, b_{2}, c_{5}, b_{4}, c_{3}, b_{3})\), \((b_{1}, c_{2}, b_{2}, c_{1}, b_{3}, c_{4})\) and \((a_{1}, c_{2}, b_{3}, c_{5}, b_{1}, c_{3})\).
(1, 8, 0): \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{2}, c_{1}, b_{3})\), \((a_{1}, b_{4}, c_{5}, b_{5})\), \((b_{1}, c_{2}, b_{3}, c_{4})\), \((b_{2}, c_{3}, b_{3}, c_{5})\), \((b_{4}, c_{4}, b_{5}, c_{1})\), \((a_{1}, c_{3}, b_{1}, c_{5})\), \((a_{1}, c_{2}, b_{2}, c_{4})\) and \((b_{4}, c_{2}, b_{5}, c_{3})\).
(1, 5, 2): \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{2}, c_{1}, b_{3})\), \((a_{1}, b_{4}, c_{5}, b_{5})\), \((b_{1}, c_{2}, b_{3}, c_{4})\), \((b_{2}, c_{3}, b_{3}, c_{5})\), \((b_{4}, c_{4}, b_{5}, c_{1})\), \((b_{1}, c_{3}, b_{4}, c_{2}, a_{1}, c_{5})\) and \((b_{2}, c_{2}, b_{5}, c_{3}, a_{1}, c_{4})\).
(1, 2, 4): \((a_{1}, b_{1}, c_{1})\), \((b_{1}, c_{2}, b_{3}, c_{4})\), \((b_{4}, c_{4}, b_{5}, c_{1})\), \((b_{1}, c_{3}, b_{4}, c_{2}, a_{1}, c_{5})\), \((b_{2}, c_{2}, b_{5}, c_{3}, a_{1}, c_{4})\), \((a_{1}, b_{2}, c_{1}, b_{3}, c_{5}, b_{4})\) and \((a_{1}, b_{3}, c_{3}, b_{2}, c_{5}, b_{5})\).
Thus there exists a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of the graph \(K_{1, 5, 5}\) for all admissible triplets \((p, q, r)\). ◻
Lemma 6. There exists a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of \(K_{1, 7, 7}\).
Proof. In order to prove the existence of \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of \(K_{1, 7, 7}\) we consider the following admissible triplets:
(7, 0, 7): Seven \(3\)-cycles are as follows: by \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{2}, c_{2})\), \((a_{1}, b_{3}, c_{3})\), \((a_{1}, b_{4}, c_{4})\), \((a_{1}, b_{5}, c_{5})\), \((a_{1}, b_{6}, c_{6})\) and \((a_{1}, b_{7}, c_{7})\). Seven \(6\)-cycles are \((b_{1}, c_{2}, b_{7}, c_{6}, b_{5}, c_{3})\), \((b_{1}, c_{4}, b_{5}, c_{7}, b_{2}, c_{5})\), \((b_{1}, c_{7}, b_{6}, c_{1}, b_{2}, c_{6})\), \((b_{3}, c_{2}, b_{6}, c_{5}, b_{4}, c_{7})\), \((b_{2}, c_{3}, b_{7}, c_{5}, b_{3}, c_{4})\), \((b_{3}, c_{1}, b_{5}, c_{2}, b_{4}, c_{6})\) and \((b_{4}, c_{1}, b_{7}, c_{4}, b_{6}, c_{3})\).
(7, 3, 5): Seven \(3\)-cycles are same as above. Required \(4\)-cycles are \((b_{3}, c_{1}, b_{5}, c_{2})\), \((b_{3}, c_{6}, b_{4}, c_{7})\) and \((b_{4}, c_{2}, b_{6}, c_{5})\). Five edge disjoint \(6\)-cycles are given by, \((b_{1}, c_{2}, b_{7}, c_{6}, b_{5}, c_{3})\), \((b_{1}, c_{4}, b_{5}, c_{7}, b_{2}, c_{5})\), \((b_{1}, c_{7}, b_{6}, c_{1}, b_{2}, c_{6})\), \((b_{2}, c_{3}, b_{7}, c_{5}, b_{3}, c_{4})\) and \((b_{4}, c_{1}, b_{7}, c_{4}, b_{6}, c_{3})\).
(7, 6, 3): The seven \(3\)-cycles are as follows: \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{2}, c_{2})\), \((a_{1}, b_{3}, c_{3})\), \((a_{1}, b_{4}, c_{4})\), \((a_{1}, b_{5}, c_{5})\), \((a_{1}, b_{6}, c_{6})\) and \((a_{1}, b_{7}, c_{7})\). Six \(4\)-cycles are \((b_{3}, c_{1}, b_{5}, c_{2})\), \((b_{3}, c_{6}, b_{4}, c_{7})\), \((b_{4}, c_{2}, b_{6}, c_{5})\), \((b_{1}, c_{4}, b_{5}, c_{7})\), \((b_{1}, c_{6}, b_{2}, c_{5})\) and \((b_{2}, c_{1}, b_{6}, c_{7})\). \(6\)-cycles in the required decomposition are given by, \((b_{1}, c_{2}, b_{7}, c_{6}, b_{5}, c_{3})\), \((b_{2}, c_{3}, b_{7}, c_{5}, b_{3}, c_{4})\) and \((b_{4}, c_{1}, b_{7}, c_{4}, b_{6}, c_{3})\).
(7, 9, 1): \((b_{3}, c_{1}, b_{5}, c_{2})\), \((b_{3}, c_{6}, b_{4}, c_{7})\), \((b_{4}, c_{2}, b_{6}, c_{5})\), \((b_{1}, c_{4}, b_{5}, c_{7})\), \((b_{1}, c_{6}, b_{2}, c_{5})\), \((b_{2}, c_{1}, b_{6}, c_{7})\), \((b_{3}, c_{4}, b_{7}, c_{5})\), \((b_{4}, c_{1}, b_{7}, c_{3})\) and \((b_{2}, c_{3}, b_{6}, c_{4})\) are the nine \(4\)-cycles and the required \(6\)-cycle is given by \((b_{1}, c_{2}, b_{7}, c_{6}, b_{5}, c_{3})\). Required \(3\)-cycles are same as above.
(5, 0, 8): \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{4}, c_{4})\), \((a_{1}, b_{5}, c_{5})\), \((a_{1}, b_{6}, c_{6})\) and \((a_{1}, b_{7}, c_{7})\) are the five copies of \(C_{3}\). Required \(6\)-cycles are given by, \((a_{1}, c_{2}, b_{7}, c_{6}, b_{5}, c_{3})\), \((a_{1}, b_{2}, c_{2}, b_{1}, c_{3}, b_{3})\), \((b_{1}, c_{4}, b_{5}, c_{7}, b_{2}, c_{5})\), \((b_{1}, c_{7}, b_{6}, c_{1}, b_{2}, c_{6})\), \((b_{3}, c_{2}, b_{6}, c_{5}, b_{4}, c_{7})\), \((b_{2}, c_{3}, b_{7}, c_{5}, b_{3}, c_{4})\), \((b_{3}, c_{1}, b_{5}, c_{2}, b_{4}, c_{6})\) and \((b_{4}, c_{1}, b_{7}, c_{4}, b_{6}, c_{3})\).
(5, 3, 6): Three copies of \(4\)-cycles are \((b_{3}, c_{1}, b_{5}, c_{6})\), \((b_{4}, c_{2}, b_{7}, c_{6})\) and \((a_{1}, c_{2}, b_{5}, c_{3})\). The six copies of \(C_{6}\) are \((a_{1}, b_{2}, c_{2}, b_{1}, c_{3}, b_{3})\), \((b_{1}, c_{4}, b_{5}, c_{7}, b_{2}, c_{5})\), \((b_{1}, c_{7}, b_{6}, c_{1}, b_{2}, c_{6})\), \((b_{3}, c_{2}, b_{6}, c_{5}, b_{4}, c_{7})\), \((b_{2}, c_{3}, b_{7}, c_{5}, b_{3}, c_{4})\) and \((b_{4}, c_{1}, b_{7}, c_{4}, b_{6}, c_{3})\). Five copies of \(3\)-cycles are same as above.
(5, 6, 4): Five copies of \(3\)-cycles are \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{4}, c_{4})\), \((a_{1}, b_{5}, c_{5})\), \((a_{1}, b_{6}, c_{6})\) and \((a_{1}, b_{7}, c_{7})\). Six copies of \(C_{4}\) are given by, \((b_{3}, c_{1}, b_{5}, c_{6})\), \((b_{4}, c_{2}, b_{7}, c_{6})\), \((a_{1}, c_{2}, b_{5}, c_{3})\), \((a_{1}, b_{2}, c_{4}, b_{3})\), \((b_{1}, c_{2}, b_{2}, c_{3})\) and \((b_{3}, c_{3}, b_{7}, c_{5})\). Four edge disjoint copies of \(6\)-cycles are \((b_{1}, c_{4}, b_{5}, c_{7}, b_{2}, c_{5})\), \((b_{1}, c_{7}, b_{6}, c_{1}, b_{2}, c_{6})\), \((b_{3}, c_{2}, b_{6}, c_{5}, b_{4}, c_{7})\) and \((b_{4}, c_{1}, b_{7}, c_{4}, b_{6}, c_{3})\).
(5, 9, 2): Five copies of \(3\)-cycles are same as above. Nine copies of \(4\)-cycles are \((b_{3}, c_{1}, b_{5}, c_{6})\), \((b_{4}, c_{2}, b_{7}, c_{6})\), \((a_{1}, c_{2}, b_{5}, c_{3})\), \((a_{1}, b_{2}, c_{4}, b_{3})\), \((b_{1}, c_{2}, b_{2}, c_{3})\), \((b_{3}, c_{3}, b_{7}, c_{5})\), \((b_{1}, c_{4}, b_{5}, c_{7})\), \((b_{1}, c_{6}, b_{2}, c_{5})\) and \((b_{2}, c_{1}, b_{6}, c_{7})\). Two copies of \(6\)-cycles are \((b_{3}, c_{2}, b_{6}, c_{5}, b_{4}, c_{7})\) and \((b_{4}, c_{1}, b_{7}, c_{4}, b_{6}, c_{3})\).
(5, 12, 0): \((b_{3}, c_{1}, b_{5}, c_{6})\), \((b_{4}, c_{2}, b_{7}, c_{6})\), \((a_{1}, c_{2}, b_{5}, c_{3})\), \((a_{1}, b_{2}, c_{4}, b_{3})\), \((b_{1}, c_{2}, b_{2}, c_{3})\), \((b_{3}, c_{3}, b_{7}, c_{5})\), \((b_{1}, c_{4}, b_{5}, c_{7})\), \((b_{1}, c_{5}, b_{2}, c_{6})\), \((b_{2}, c_{1}, b_{4}, c_{7})\), \((b_{3}, c_{2}, b_{6}, c_{7})\), \((b_{6}, c_{1}, b_{7}, c_{4})\) and \((b_{4}, c_{3}, b_{6}, c_{5})\) are the required \(4\)-cycles. Five copies of \(3\)-cycles are \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{4}, c_{4})\), \((a_{1}, b_{5}, c_{5})\), \((a_{1}, b_{6}, c_{6})\) and \((a_{1}, b_{7}, c_{7})\).
(3, 0, 9): Three copies of \(3\)-cycles are \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{6}, c_{6})\) and \((a_{1}, b_{7}, c_{7})\). Nine edge disjoint
copies of \(6\)-cycles are given by,
\((a_{1}, c_{2}, b_{3}, c_{1}, b_{5},
c_{3})\), \((b_{3}, c_{6}, b_{5},
c_{2}, b_{6}, c_{7})\), \((b_{1},
c_{5}, b_{3}, c_{3}, b_{7}, c_{6})\), \((b_{2}, c_{5}, b_{7}, c_{2}, b_{4},
c_{6})\), \((a_{1}, b_{2}, c_{2},
b_{1}, c_{4}, b_{3})\), \((b_{1},
c_{3}, b_{2}, c_{4}, b_{5}, c_{7})\), \((b_{2}, c_{1}, b_{7}, c_{4}, b_{4},
c_{7})\),
\((a_{1}, b_{4}, c_{1}, b_{6}, c_{5},
b_{5})\) and \((a_{1}, c_{4}, b_{6},
c_{3}, b_{4}, c_{5})\).
(3, 3, 7): Required copies of \(3\)-cycles are same as above. Three copies of \(4\)-cycles are \((b_{3}, c_{1}, b_{5}, c_{6})\), \((b_{3}, c_{2}, b_{6}, c_{7})\) and \((a_{1}, c_{2}, b_{5}, c_{3})\). \(6\)-cycles in the required decomposition are \((b_{1}, c_{5}, b_{3}, c_{3}, b_{7}, c_{6})\), \((b_{2}, c_{5}, b_{7}, c_{2}, b_{4}, c_{6})\), \((a_{1}, b_{2}, c_{2}, b_{1}, c_{4}, b_{3})\), \((b_{1}, c_{3}, b_{2}, c_{4}, b_{5}, c_{7})\), \((b_{2}, c_{1}, b_{7}, c_{4}, b_{4}, c_{7})\), \((a_{1}, b_{4}, c_{1}, b_{6}, c_{5}, b_{5})\) and \((a_{1}, c_{4}, b_{6}, c_{3}, b_{4}, c_{5})\).
(3, 6, 5): \((b_{3}, c_{1}, b_{5}, c_{6})\), \((b_{3}, c_{2}, b_{6}, c_{7})\), \((a_{1}, c_{2}, b_{5}, c_{3})\), \((b_{4}, c_{2}, b_{7}, c_{6})\), \((b_{1}, c_{5}, b_{2}, c_{6})\) and \((b_{3}, c_{3}, b_{7}, c_{5})\) are the required copies of \(4\)-cycles. Five copies of \(6\)-cycles are given by, \((a_{1}, b_{2}, c_{2}, b_{1}, c_{4}, b_{3})\), \((b_{1}, c_{3}, b_{2}, c_{4}, b_{5}, c_{7})\), \((b_{2}, c_{1}, b_{7}, c_{4}, b_{4}, c_{7})\), \((a_{1}, b_{4}, c_{1}, b_{6}, c_{5}, b_{5})\) and \((a_{1}, c_{4}, b_{6}, c_{3}, b_{4}, c_{5})\). Two copies of \(3\)-cycles in the required decomposition are \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{6}, c_{6})\) and \((a_{1}, b_{7}, c_{7})\).
(3, 9, 3): Three copies of \(3\)-cycles are same as above. Nine edge disjoint copies of \(4\)-cycles are given by \((b_{3}, c_{1}, b_{5}, c_{6})\), \((b_{3}, c_{2}, b_{6}, c_{7})\), \((a_{1}, c_{2}, b_{5}, c_{3})\), \((b_{4}, c_{2}, b_{7}, c_{6})\), \((b_{1}, c_{5}, b_{2}, c_{6})\), \((b_{3}, c_{3}, b_{7}, c_{5})\), \((a_{1}, b_{2}, c_{4}, b_{3})\), \((b_{1}, c_{2}, b_{2}, c_{3})\) and \((b_{1}, c_{4}, b_{5}, c_{7})\). Required copies of \(6\)-cycles are \((b_{2}, c_{1}, b_{7}, c_{4}, b_{4}, c_{7})\), \((a_{1}, b_{4}, c_{1}, b_{6}, c_{5}, b_{5})\) and \((a_{1}, c_{4}, b_{6}, c_{3}, b_{4}, c_{5})\).
(3, 12, 1): Twelve edge disjoint copies of \(4\)-cycles are \((b_{3}, c_{1}, b_{5}, c_{6})\), \((b_{3}, c_{2}, b_{6}, c_{7})\), \((a_{1}, c_{2}, b_{5}, c_{3})\), \((b_{4}, c_{2}, b_{7}, c_{6})\), \((b_{1}, c_{5}, b_{2}, c_{6})\), \((b_{3}, c_{3}, b_{7}, c_{5})\), \((a_{1}, b_{2}, c_{4}, b_{3})\), \((b_{1}, c_{2}, b_{2}, c_{3})\), \((b_{1}, c_{4}, b_{5}, c_{7})\), \((b_{2}, c_{1}, b_{4}, c_{7})\), \((a_{1}, c_{4}, b_{4}, c_{5})\) and \((b_{6}, c_{1}, b_{7}, c_{4})\). Required \(C_{6}\) is \((a_{1}, b_{4}, c_{3}, b_{6}, c_{5}, b_{5})\). Three copies of \(3\)-cycles are \((a_{1}, b_{1}, c_{1})\), \((a_{1}, b_{6}, c_{6})\) and \((a_{1}, b_{7}, c_{7})\).
(1, 0, 10): \((a_{1}, b_{1}, c_{1})\) is the required \(C_{3}\). Ten edge disjoint copies of \(6\)-cycles are \((a_{1}, c_{2}, b_{3}, c_{1}, b_{5}, c_{3})\), \((b_{3}, c_{6}, b_{5}, c_{2}, b_{6}, c_{7})\), \((b_{1}, c_{5}, b_{3}, c_{3}, b_{7}, c_{6})\), \((b_{2}, c_{5}, b_{7}, c_{2}, b_{4}, c_{6})\), \((a_{1}, b_{2}, c_{2}, b_{1}, c_{4}, b_{3})\), \((b_{1}, c_{3}, b_{2}, c_{4}, b_{5}, c_{7})\), \((a_{1}, c_{4}, b_{4}, c_{3}, b_{6}, c_{6})\), \((a_{1}, b_{4}, c_{7}, b_{2}, c_{1}, b_{6})\), \((a_{1}, c_{5}, b_{6}, c_{4}, b_{7}, c_{7})\) and \((a_{1}, b_{5}, c_{5}, b_{4}, c_{1}, b_{7})\).
(1, 3, 8): \((b_{3}, c_{1}, b_{5}, c_{6})\), \((b_{3}, c_{2}, b_{6}, c_{7})\) and \((a_{1}, c_{2}, b_{5}, c_{3})\) are the 3 edge disjoint copies of \(4\)-cycles. Required \(6\)-cycles are \((b_{1}, c_{5}, b_{3}, c_{3}, b_{7}, c_{6})\), \((b_{2}, c_{5}, b_{7}, c_{2}, b_{4}, c_{6})\), \((a_{1}, b_{2}, c_{2}, b_{1}, c_{4}, b_{3})\), \((b_{1}, c_{3}, b_{2}, c_{4}, b_{5}, c_{7})\), \((a_{1}, c_{4}, b_{4}, c_{3}, b_{6}, c_{6})\), \((a_{1}, b_{4}, c_{7}, b_{2}, c_{1}, b_{6})\), \((a_{1}, c_{5}, b_{6}, c_{4}, b_{7}, c_{7})\) and \((a_{1}, b_{5}, c_{5}, b_{4}, c_{1}, b_{7})\). The required \(C_{3}\) is \((a_{1}, b_{1}, c_{1})\).
(1, 6, 6): One copy of \(C_{3}\) is given by, \((a_{1}, b_{1}, c_{1})\). Required \(4\)-cycles are as follows: \((b_{3}, c_{1}, b_{5}, c_{6})\), \((b_{3}, c_{2}, b_{6}, c_{7})\), \((a_{1}, c_{2}, b_{5}, c_{3})\), \((b_{4}, c_{2}, b_{7}, c_{6})\), \((b_{1}, c_{5}, b_{2}, c_{6})\) and \((b_{3}, c_{3}, b_{7}, c_{5})\). \(6\)-cycles in the required decomposition are given by, \((a_{1}, b_{2}, c_{2}, b_{1}, c_{4}, b_{3})\), \((b_{1}, c_{3}, b_{2}, c_{4}, b_{5}, c_{7})\), \((a_{1}, c_{4}, b_{4}, c_{3}, b_{6}, c_{6})\), \((a_{1}, b_{4}, c_{7}, b_{2}, c_{1}, b_{6})\), \((a_{1}, c_{5}, b_{6}, c_{4}, b_{7}, c_{7})\) and \((a_{1}, b_{5}, c_{5}, b_{4}, c_{1}, b_{7})\).
(1, 9, 4): \((a_{1}, b_{1}, c_{1})\) is the required \(C_{3}\). Nine copies of \(4\)-cycles are as follows: \((b_{3}, c_{1}, b_{5}, c_{6})\), \((b_{3}, c_{2}, b_{6}, c_{7})\), \((a_{1}, c_{2}, b_{5}, c_{3})\), \((b_{4}, c_{2}, b_{7}, c_{6})\), \((b_{1}, c_{5}, b_{2}, c_{6})\), \((b_{3}, c_{3}, b_{7}, c_{5})\), \((a_{1}, b_{2}, c_{4}, b_{3})\), \((b_{1}, c_{2}, b_{2}, c_{3})\) and \((b_{1}, c_{4}, b_{5}, c_{7})\). Required \(6\)-cycles are as follows: \((a_{1}, c_{4}, b_{4}, c_{3}, b_{6}, c_{6})\), \((a_{1}, b_{4}, c_{7}, b_{2}, c_{1}, b_{6})\), \((a_{1}, c_{5}, b_{6}, c_{4}, b_{7}, c_{7})\) and \((a_{1}, b_{5}, c_{5}, b_{4}, c_{1}, b_{7})\).
(1, 12, 2): \((a_{1},
b_{1}, c_{1})\) is the required \(C_{3}\). Twelve copies of \(4\)-cycles are as follows: \((b_{3}, c_{1}, b_{5}, c_{6})\), \((b_{3}, c_{2}, b_{6}, c_{7})\), \((a_{1}, c_{2}, b_{5}, c_{3})\), \((b_{4}, c_{2}, b_{7}, c_{6})\), \((b_{1}, c_{5}, b_{2}, c_{6})\), \((b_{3}, c_{3}, b_{7}, c_{5})\), \((a_{1}, b_{2}, c_{4}, b_{3})\),
\((b_{1}, c_{2}, b_{2}, c_{3})\), \((b_{1}, c_{4}, b_{5}, c_{7})\), \((a_{1}, c_{4}, b_{7}, c_{7})\), \((a_{1}, b_{4}, c_{3}, b_{6})\) and \((a_{1}, c_{5}, b_{6}, c_{6})\). \(6\)-cycles in the required decomposition is
given by, \((b_{2}, c_{1}, b_{6}, c_{4},
b_{4}, c_{7})\) and \((a_{1}, b_{5},
c_{5}, b_{4}, c_{1}, b_{7})\).
(1, 15, 0): Required \(4\)-cycles are given by: \((b_{3}, c_{1}, b_{5}, c_{6})\), \((b_{3}, c_{2}, b_{6}, c_{7})\), \((a_{1}, c_{2}, b_{5}, c_{3})\), \((b_{4}, c_{2}, b_{7}, c_{6})\), \((b_{1}, c_{5}, b_{2}, c_{6})\), \((b_{3}, c_{3}, b_{7}, c_{5})\), \((a_{1}, b_{2}, c_{4}, b_{3})\), \((b_{1}, c_{2}, b_{2}, c_{3})\), \((b_{1}, c_{4}, b_{5}, c_{7})\), \((a_{1}, c_{5}, b_{6}, c_{6})\), \((b_{4}, c_{3}, b_{6}, c_{4})\), \((a_{1}, c_{4}, b_{7}, c_{7})\), \((a_{1}, b_{4}, c_{5}, b_{5})\), \((a_{1}, b_{6}, c_{1}, b_{7})\) and \((b_{2}, c_{1}, b_{4}, c_{7})\). The \(C_{3}\) in the required decomposition is \((a_{1}, b_{1}, c_{1})\).
Thus the graph \(K_{1, 7, 7}\) admits a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition for all admissible triplets \((p, q, r)\). ◻
Theorem 4. The graph \(K_{1, m, m}\) where \(m\) is odd, admits a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition where \(1 \leq p \leq m\) and \(3p + 4q +6r = m^{2} + 2m\).
Proof. The graph \(K_{1, m, m}\) has \(m^{2} + 2m\) edges. Since \(m\) is odd, here \(p \neq 0\). Consider the case \(m \equiv 1 (\)mod\(\ 4)\). Let \(m = 4n + 1\). Here,
\[K_{1, m, m} = (a_{1}, b_{1}, c_{1}) \oplus \underbrace{(K_{1, 5, 5} – C_{3}) \oplus (K_{1, 5, 5} – C_{3}) \oplus … \oplus (K_{1, 5, 5} – C_{3})} _\text{n copies} \oplus \underbrace{(K_{4, 4}) \oplus (K_{4, 4}) \oplus … \oplus (K_{4, 4})} _\text{n(n – 1) copies}.\]
By Lemma 5, the graph \(K_{1, 5, 5} – C_{3}\) admits a \((C_{3}, C_{4}, C_{6})\) decomposition for all admissible triplets. Theorem 2 guarantees the existence of \((C_{4}, C_{6})\)– cycle decomposition of \(K_{4, 4}\) for all admissible pairs \((q^{'}, r^{'})\). Now consider the case \(m \equiv 3(\)mod\(\ 4)\). Let \(m = 4n + 3\). In this case,
\[\begin{aligned} K_{1, m, m} =& (a_{1}, b_{1}, c_{1}) \oplus (K_{1, 7, 7} – C_{3}) \, \oplus \underbrace{(K_{1, 5, 5} – C_{3}) \oplus (K_{1, 5, 5} – C_{3}) \oplus … \oplus (K_{1, 5, 5} – C_{3})} _\text{(n – 1) copies}\\ & \oplus \underbrace{(K_{4, 6}) \oplus (K_{4, 6}) \oplus … \oplus (K_{4, 6})} _\text{2(n – 1) copies}. \end{aligned}\]
By Lemmas 5 and 6, the graph \(K_{1, 5, 5} – C_{3}\) and \(K_{1, 7, 7} – C_{3}\) 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 \(K_{1, m, m}\) can be decomposed into \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\) for all admissible triplets \((p, q, r)\). ◻
Lemma 7. There exists a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of the graph \(K_{\ell, \ell, m}.\)
Proof. The graph \(K_{\ell, \ell, m} = K_{\ell, \ell, \ell} \oplus K_{2\ell, m – \ell}\). By Theorem 3, the graph \(K_{\ell, \ell, \ell}\) 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 \(K_{2\ell, m – \ell}\) for all possible pair \((q^{'}, r^{'})\).
It is easy to verify that whenever \(m – \ell = 2\) and \(p = \ell^{2}\) then \(r = 0\). When \(p < \ell^{2},\) then there exists \(4\)-cycles and \(6\)-cycles for all possible triplets \((p, q, r)\).
Thus the graph \(K_{\ell, \ell, m}\) can be decomposed into \(p\) copies of \(C_{3}\), \(q\) copies of \(C_{4}\) and \(r\) copies of \(C_{6}\) for all admissible triplets \((p, q, r).\) ◻
Lemma 8. The graph \(K_{\ell, m, m}\) with \(m – \ell \equiv 0(\)mod\(\ 4)\) has a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition.
Proof. Let \(\{a_{1}, a_{2}, …, a_{l}\}, \{b_{1}, b_{2}, …, b_{m}\}\) and \(\{c_{1}, c_{2}, …, c_{m}\}\) be the partite sets of \(K_{\ell, 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 \(\ell\) rows of the latin square corresponds to the maximum possible cycles of length 3. Thus \(p = \ell m\) is achieved. Further, the entries in the first \(\ell\) rows of the latin square can be then partitioned into \(2 \times 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^{\prime}, q^{\prime}, r^{\prime} )\) similar to Case 1 or Case 2 of Theorem 3, according as \(\ell\) even or odd.
Next, we consider the remaining \(m – \ell\) rows of the latin square, where the entries will be of the form,
| 1 | 2 | 3 | 4 | \(\cdots\) | \(m-1\) | \(m\) |
| \(\ell+1\) | \(\ell+2\) | \(\ell+3\) | \(\ell+4\) | \(\cdots\) | \(\ell-1\) | \(\ell\) |
| \(\ell+2\) | \(\ell+3\) | \(\ell+4\) | \(\ell+5\) | \(\cdots\) | \(\ell\) | \(\ell+1\) |
| \(\ell+3\) | \(\ell+4\) | \(\ell+5\) | \(\ell+6\) | \(\cdots\) | \(\ell+1\) | \(\ell+2\) |
| \(\ell+4\) | \(\ell+5\) | \(\ell+6\) | \(\ell+7\) | \(\cdots\) | \(\ell+2\) | \(\ell+3\) |
Note that each entry in the remaining \(m – \ell\) rows represent an edge between the second and third partite sets. We first decompose the edges corresponding to the entries in these \(m – \ell\) rows of the latin square into \(C_{4}\). Consider a block of first four rows, say rows \(\ell+1,\,\ell+2,\,\ell+3,\,\ell+4.\) The entries in the rows correspond to \(4m\) edges and are decomposed into copies of \(C_{4}\) as follows: For example, we consider the bold entries as shown above, which corresponds to a \(4\)-cycle \((b_{1}, c_{\ell + 1}, b_{m – 1}, c_{\ell + 2})\). Similarly, the underlined entries and the entries in the rectangular box corresponds to the \(4\)-cycles \((b_{1}, c_{\ell + 3}, b_{3}, c_{\ell + 4})\) and \((b_{2}, c_{\ell + 2}, b_{m}, c_{\ell + 3}),\) respectively. These three cycles of length four are taken together to have two copies of \(C_{6}\) and are given by \((b_{1}, c_{\ell + 1}, b_{m – 1}, c_{\ell + 2}, b_{m}, c_{\ell + 3})\) and \((b_{1}, c_{\ell + 2}, b_{2}, c_{\ell + 3}, b_{3}, c_{\ell + 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 \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of the graph \(K_{\ell, m, m}\) with \(m – \ell \equiv 0(\)mod\(\ 4)\). ◻
Lemma 9. For \(p = \ell(\ell + 2)\) and \(4q + 6r = 2(\ell + 2)\), the graph \(K_{\ell, \, \ell + 2, \, \ell + 2}\) admits a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition.
Proof. Consider the bipartite graph \(K_{\ell + 2, \, \ell + 2},\) a proper subgraph of \(K_{\ell, \, \ell + 2, \, \ell + 2}.\) The degree of each vertex in \(K_{\ell + 2, \, \ell + 2}\) is \(\ell + 2\). From this complete bipartite graph, we first construct a \(2\)-factor \(\mathcal{F}\) consisting \(q\) copies of \(C_{4}\) and \(r\) copies of \(C_{6}\). For this, we consider base cycles \(C = b_{1}c_{1}b_{2}c_{2}\) and \(C^{'} = b_{2q+1}c_{2q+1}b_{2q+2}c_{2q+2}b_{2q+3}c_{2q+3}\). Then the \(2\)-factor \(\mathcal{F}\) is given by \[\{\rho^{0}(C), \rho^{2}(C), …, \rho^{2q-2}(C)\} \bigcup \{\rho^{0}(C^{'}), \rho^{3}(C^{'}), …, \rho^{\ell-2q-1}(C^{'})\}.\] Now, if we decompose the graph \((K_{\ell,\,\ell+2,\,\ell+2}-\mathcal{F})\) into \(\ell(\ell+2)\) copies of \(3\)-cycles, then we are done. This can be achieved as follows: after the removal of \(\mathcal{F}\) and \(\ell(\ell + 2)\) copies of \(3\)-cycles from \(K_{\ell, \, \ell + 2, \, \ell + 2},\) the edges in between second and third partite sets can be decomposed into \(1\)-factors \(F_{1}, F_{2}, …, F_{\ell}.\) Now, for \(1\le i\le \ell,\) the edges incident with a vertex \(a_{i}\) together with a \(1\)-factor \(F_{i}\) would yield a \(C_{3}\)-factor, which completes the proof of this lemma. ◻
In order to prove the existence of \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of \(K_{\ell, m, m}\) with \(m – \ell \equiv 2 (mod \, 4)\), we use a latin square which is constructed from an idempotent latin square. Since there is no idempotent latin square of order \(2 \times 2\), we now prove the existence of \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of the graph \(K_{3, 5, 5}\).
Lemma 10. The graph \(K_{3, 5, 5}\) admits a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition.
Proof. In order to prove the existence of \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of \(K_{3, 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 \(K_{3, 5, 5}\) is \(15\) which are as follows: \((a_{1}, b_{1}, c_{3})\), \((a_{1}, b_{2}, c_{4})\), \((a_{1}, b_{3}, c_{1})\), \((a_{1}, b_{4}, c_{5})\), \((a_{1}, b_{5}, c_{2})\), \((a_{2}, b_{1}, c_{5})\), \((a_{2}, b_{2}, c_{3})\), \((a_{2}, b_{3}, c_{4})\), \((a_{2}, b_{4}, c_{2})\), \((a_{2}, b_{5}, c_{1})\), \((a_{3}, b_{1}, c_{4})\), \((a_{3}, b_{2}, c_{5})\), \((a_{3}, b_{3}, c_{2})\), \((a_{3}, b_{4}, c_{1})\) and \((a_{3}, b_{5}, c_{3})\). The remaining 10 edges from second and third partite which can be decomposed into a \(C_{4}\) and \(C_{6}\) given by, \((b_{1}, c_{2}, b_{2}, c_{1})\) and \((b_{3}, c_{3}, b_{4}, c_{4}, b_{5}, c_{5})\).
(13, 4, 0): Required edge disjoint copies of \(3\)-cycles are \((a_{1}, b_{2}, c_{4})\), \((a_{1}, b_{3}, c_{1})\), \((a_{1}, b_{5}, c_{2})\), \((a_{2}, b_{1}, c_{5})\), \((a_{2}, b_{2}, c_{3})\), \((a_{2}, b_{3}, c_{4})\), \((a_{2}, b_{4}, c_{2})\), \((a_{2}, b_{5}, c_{1})\), \((a_{3}, b_{1}, c_{4})\), \((a_{3}, b_{2}, c_{5})\), \((a_{3}, b_{3}, c_{2})\), \((a_{3}, b_{4}, c_{1})\) and \((a_{3}, b_{5}, c_{3})\). Four copies of \(4\)-cycles are \((b_{1}, c_{1}, b_{2}, c_{2})\), \((b_{4}, c_{4}, b_{5}, c_{5})\), \((a_{1}, b_{1}, c_{3}, b_{4})\) and \((a_{1}, c_{3}, b_{3}, c_{5})\).
(13, 1, 2): Edge disjoint copies of \(3\)-cycles are same as above. Required \(C_{4}\) is given by \((b_{1}, c_{1}, b_{2}, c_{2})\). Two copies of \(6\)-cycles are \((a_{1}, b_{1}, c_{3}, b_{3}, c_{5}, b_{4})\) and \((a_{1}, c_{3}, b_{4}, c_{4}, b_{5}, c_{5})\).
(11, 4, 1): Required copies of \(3\)-cycles are given by, \((a_{1}, b_{2}, c_{4})\), \((a_{1}, b_{3}, c_{1})\), \((a_{1}, b_{5}, c_{2})\), \((a_{2}, b_{2}, c_{3})\), \((a_{2}, b_{3}, c_{4})\), \((a_{2}, b_{5}, c_{1})\), \((a_{3}, b_{1}, c_{4})\), \((a_{3}, b_{2}, c_{5})\), \((a_{3}, b_{3}, c_{2})\), \((a_{3}, b_{4}, c_{1})\) and \((a_{3}, b_{5}, c_{3})\). Four copies of \(4\)-cycles are \((a_{2}, c_{2}, b_{1}, c_{5})\), \((b_{4}, c_{4}, b_{5}, c_{5})\), \((a_{2}, b_{1}, c_{3}, b_{4})\) and \((a_{1}, c_{3}, b_{3}, c_{5})\). Required \(C_{6}\) is \((a_{1}, b_{1}, c_{1}, b_{2}, c_{2}, b_{4})\).
(11, 1, 3): Required copies of \(3\)-cycles will be the same as given above. Three copies of \(6\)-cycles are \((b_{3}, c_{3}, b_{4}, c_{4}, b_{5}, c_{5})\), \((a_{2}, c_{2}, b_{4}, a_{1}, b_{1}, c_{5})\) and \((a_{1}, c_{3}, b_{1}, a_{2}, b_{4}, c_{5})\). Required \(C_{4}\) is \((b_{1}, c_{1}, b_{2}, c_{2})\).
(9, 7, 0): Seven copies of \(4\)-cycles are as follows, \((b_{1}, c_{1}, b_{2}, c_{2})\), \((a_{1}, c_{3}, b_{4}, c_{5})\), \((a_{1}, b_{4}, c_{2}, b_{5})\), \((a_{1}, b_{1}, a_{2}, c_{2})\), \((b_{1}, c_{3}, b_{3}, c_{5})\), \((a_{2}, b_{3}, c_{4}, b_{4})\) and \((a_{2}, c_{4}, b_{5}, c_{5})\). Required copies of \(3\)-cycles are given by \((a_{1}, b_{2}, c_{4})\), \((a_{1}, b_{3}, c_{1})\), \((a_{2}, b_{2}, c_{3})\), \((a_{2}, b_{5}, c_{1})\), \((a_{3}, b_{1}, c_{4})\), \((a_{3}, b_{2}, c_{5})\), \((a_{3}, b_{3}, c_{2})\), \((a_{3}, b_{4}, c_{1})\) and \((a_{3}, b_{5}, c_{3})\).
(9, 4, 2): Nine copies of \(3\)-cycles are given by \((a_{1}, b_{2}, c_{4})\), \((a_{1}, b_{3}, c_{1})\), \((a_{2}, b_{2}, c_{3})\), \((a_{2}, b_{5}, c_{1})\), \((a_{3}, b_{1}, c_{4})\), \((a_{3}, b_{2}, c_{5})\), \((a_{3}, b_{3}, c_{2})\), \((a_{3}, b_{4}, c_{1})\) and \((a_{3}, b_{5}, c_{3})\). Four edge disjoint copies of \(4\)-cycles are \((b_{1}, c_{1}, b_{2}, c_{2})\), \((a_{1}, c_{3}, b_{4}, c_{5})\), \((a_{2}, b_{3}, c_{4}, b_{4})\) and \((b_{1}, c_{3}, b_{3}, c_{5})\). Required \(6\)-cycles are \((a_{1}, b_{1}, a_{2}, c_{4}, b_{5}, c_{2})\) and \((a_{1}, b_{4}, c_{2}, a_{2}, c_{5}, b_{5})\).
(9, 1, 4): Required copies of \(3\)-cycles are same as given above. \((b_{1}, c_{1}, b_{2}, c_{2})\) is the required \(C_{4}\). Edge disjoint copies of \(6\)-cycles are as follows: \((a_{1}, b_{1}, a_{2}, c_{4}, b_{5}, c_{2})\), \((a_{1}, b_{4}, c_{2}, a_{2}, c_{5}, b_{5})\), \((a_{1}, c_{3}, b_{3}, a_{2}, b_{4}, c_{5})\) and \((b_{1}, c_{3}, b_{4}, c_{4}, b_{3}, c_{5})\).
(7, 7, 1): \((a_{1}, b_{2}, c_{4})\), \((a_{1}, b_{3}, c_{1})\), \((a_{2}, b_{2}, c_{3})\), \((a_{2}, b_{5}, c_{1})\), \((a_{3}, b_{1}, c_{4})\), \((a_{3}, b_{2}, c_{5})\) and \((a_{3}, b_{4}, c_{1})\) are the seven edge disjoint copies of \(3\)-cycles and the required \(C_{6}\) is \((a_{2}, b_{3}, c_{5}, b_{1}, c_{3}, b_{4})\). Seven copies of \(4\)-cycles are as follows: \((b_{1}, c_{1}, b_{2}, c_{2})\), \((a_{1}, b_{1}, a_{2}, c_{5})\), \((a_{1}, b_{4}, c_{5}, b_{5})\), \((a_{2}, c_{2}, b_{4}, c_{4})\), \((a_{1}, c_{2}, b_{3}, c_{3})\), \((a_{3}, c_{2}, b_{5}, c_{3})\) and \((a_{3}, b_{3}, c_{4}, b_{5})\).
(7, 4, 3): Four copies of \(4\)-cycles are \((b_{1}, c_{1}, b_{2}, c_{2})\), \((a_{1}, b_{1}, a_{2}, c_{5})\), \((a_{1}, b_{4}, c_{5}, b_{5})\) and \((a_{2}, c_{2}, b_{4}, c_{4})\). Required \(6\)-cycles are \((a_{3}, c_{2}, b_{5}, c_{4}, b_{3}, c_{3})\), \((a_{1}, c_{2}, b_{3}, a_{3}, b_{5}, c_{3})\) and \((a_{2}, b_{3}, c_{5}, b_{1}, c_{3}, b_{4})\). Seven copies of \(3\)-cycles are same as given above.
(7, 1, 5): \((a_{3}, c_{2}, b_{5}, c_{4}, b_{3}, c_{3})\), \((a_{1}, c_{2}, b_{3}, a_{3}, b_{5}, c_{3})\), \((a_{2}, b_{3}, c_{5}, b_{1}, c_{3}, b_{4})\), \((a_{1}, b_{4}, c_{2}, a_{2}, c_{5}, b_{5})\) and \((a_{1}, b_{1}, a_{2}, c_{4}, b_{4}, c_{5})\) are the five edge disjoint copies of \(6\)-cycles required and one copy of \(C_{4}\) is \((b_{1}, c_{1}, b_{2}, c_{2})\). Required seven copies of \(3\)-cycles are \((a_{1}, b_{2}, c_{4})\), \((a_{1}, b_{3}, c_{1})\), \((a_{2}, b_{2}, c_{3})\), \((a_{2}, b_{5}, c_{1})\), \((a_{3}, b_{1}, c_{4})\), \((a_{3}, b_{2}, c_{5})\) and \((a_{3}, b_{4}, c_{1})\).
(5, 10, 0): Five copies of \(3\)-cycles are \((a_{1}, b_{2}, c_{4})\), \((a_{2}, b_{2}, c_{3})\), \((a_{3}, b_{1}, c_{4})\), \((a_{3}, b_{2}, c_{5})\) and \((a_{3}, b_{4}, c_{1})\). Ten edge disjoint copies of \(4\)-cycles are \((b_{1}, c_{3}, b_{3}, c_{5})\), \((b_{3}, c_{1}, b_{5}, c_{4})\), \((a_{1}, c_{2}, a_{3}, c_{3})\), \((a_{2}, b_{4}, c_{3}, b_{5})\), \((a_{1}, c_{1}, a_{2}, b_{3})\), \((a_{3}, b_{3}, c_{2}, b_{5})\), \((a_{1}, b_{4}, c_{5}, b_{5})\), \((a_{1}, b_{1}, a_{2}, c_{5})\), \((a_{2}, c_{2}, b_{4}, c_{4})\) and \((b_{1}, c_{1}, b_{2}, c_{2})\).
(5, 7, 2): Five copies of \(3\)-cycles are same as given above. Required \(4\)-cycle are as follows: \((a_{1}, b_{4}, c_{5}, b_{5})\), \((a_{1}, c_{2}, a_{3}, c_{3})\), \((a_{2}, b_{4}, c_{3}, b_{5})\), \((b_{3}, c_{1}, b_{5}, c_{4})\), \((a_{2}, c_{2}, b_{4}, c_{4})\), \((a_{3}, b_{3}, c_{2}, b_{5})\) and \((b_{1}, c_{1}, b_{2}, c_{2})\). \(6\)-cycles in the required decomposition are given by \((a_{1}, b_{1}, c_{3}, b_{3}, a_{2}, c_{5})\) and \((a_{1}, b_{3}, c_{5}, b_{1}, a_{2}, c_{1})\).
(5, 4, 4): \((a_{1}, b_{2}, c_{4})\), \((a_{2}, b_{2}, c_{3})\), \((a_{3}, b_{1}, c_{4})\), \((a_{3}, b_{2}, c_{5})\) and \((a_{3}, b_{4}, c_{1})\) are the five copies of \(3\)-cycles. \(4\)-cycles in the required decomposition are \((a_{1}, b_{4}, c_{5}, b_{5})\), \((b_{3}, c_{1}, b_{5}, c_{4})\), \((a_{3}, b_{3}, c_{2}, b_{5})\) and \((b_{1}, c_{1}, b_{2}, c_{2})\). Four copies of \(6\)-cycles are given by, \((a_{1}, b_{1}, c_{3}, b_{3}, a_{2}, c_{5})\), \((a_{1}, b_{3}, c_{5}, b_{1}, a_{2}, c_{1})\), \((a_{1}, c_{2}, b_{4}, a_{2}, b_{5}, c_{3})\) and \((a_{2}, c_{2}, a_{3}, c_{3}, b_{4}, c_{4})\).
(5, 1, 6): Five copies of \(3\)-cycles are same as given above. Six copies of \(6\)-cycles are \((a_{1}, b_{1}, c_{3}, b_{3}, a_{2}, c_{5})\), \((a_{1}, b_{3}, c_{5}, b_{1}, a_{2}, c_{1})\), \((a_{1}, c_{2}, b_{4}, a_{2}, b_{5}, c_{3})\), \((a_{2}, c_{2}, a_{3}, c_{3}, b_{4}, c_{4})\), \((a_{3}, b_{3}, c_{1}, b_{1}, c_{2}, b_{5})\) and \((b_{2}, c_{1}, b_{5}, c_{4}, b_{3}, c_{2})\) and one copy of \(C_{4}\) in the required decomposition is \((a_{1}, b_{4}, c_{5}, b_{5})\).
(3, 1, 7): Edge disjoint copies of \(3\)-cycles are \((a_{3}, b_{1}, c_{4})\), \((a_{3}, b_{2}, c_{5})\) and \((a_{2}, b_{2}, c_{4})\). Required copies of \(6\)-cycles are as follows: \((a_{1}, b_{1}, c_{3}, b_{3}, a_{2}, c_{5})\), \((a_{1}, b_{3}, c_{5}, b_{1}, a_{2}, c_{1})\), \((a_{1}, c_{2}, b_{4}, a_{2}, b_{5}, c_{3})\), \((b_{2}, c_{1}, b_{5}, c_{4}, b_{3}, c_{2})\), \((a_{2}, c_{2}, a_{3}, c_{1}, b_{4}, c_{3})\), \((a_{3}, b_{3}, c_{1}, b_{1}, c_{2}, b_{5})\) and \((a_{1}, b_{2}, c_{3}, a_{3}, b_{4}, c_{4})\). Required \(4\)-cycle is given by \((a_{1}, b_{4}, c_{5}, b_{5})\).
(3, 4, 5): Edge disjoint copies of \(3\)-cycles is same as given above. Required \(4\)-cycles are \((a_{1}, b_{1}, c_{3}, b_{3})\), \((a_{1}, c_{1}, a_{2}, c_{5})\), \((a_{2}, b_{1}, c_{5}, b_{3})\) and \((a_{1}, b_{4}, c_{5}, b_{5})\). Five copies of \(6\)-cycles are given by \((a_{1}, c_{2}, b_{4}, a_{2}, b_{5}, c_{3})\), \((b_{2}, c_{1}, b_{5}, c_{4}, b_{3}, c_{2})\), \((a_{2}, c_{2}, a_{3}, c_{1}, b_{4}, c_{3})\), \((a_{3}, b_{3}, c_{1}, b_{1}, c_{2}, b_{5})\) and \((a_{1}, b_{2}, c_{3}, a_{3}, b_{4}, c_{4})\).
(3, 7, 3): Seven copies of \(4\)-cycles are \((a_{1}, b_{1}, c_{3}, b_{3})\), \((a_{1}, c_{1}, a_{2}, c_{5})\), \((a_{2}, b_{1}, c_{5}, b_{3})\), \((a_{1}, b_{4}, c_{5}, b_{5})\), \((a_{1}, c_{2}, a_{2}, c_{3})\), \((a_{2}, b_{4}, c_{3}, b_{5})\) and \((a_{3}, c_{1}, b_{4}, c_{2})\). Required \(6\)-cycles are given by, \((b_{2}, c_{1}, b_{5}, c_{4}, b_{3}, c_{2})\), \((a_{3}, b_{3}, c_{1}, b_{1}, c_{2}, b_{5})\) and \((a_{1}, b_{2}, c_{3}, a_{3}, b_{4}, c_{4})\). Edge disjoint copies of \(3\)-cycles are \((a_{3}, b_{1}, c_{4})\), \((a_{3}, b_{2}, c_{5})\) and \((a_{2}, b_{2}, c_{4})\).
(3, 10, 1): \((a_{1}, b_{1}, c_{3}, b_{3})\), \((a_{1}, c_{1}, a_{2}, c_{5})\), \((a_{2}, b_{1}, c_{5}, b_{3})\), \((a_{1}, b_{4}, c_{5}, b_{5})\), \((a_{1}, c_{2}, a_{2}, c_{3})\), \((a_{2}, b_{4}, c_{3}, b_{5})\), \((a_{3}, c_{1}, b_{4}, c_{2})\), \((b_{1}, c_{1}, b_{2}, c_{2})\), \((b_{3}, c_{1}, b_{5}, c_{4})\) and \((a_{3}, b_{3}, c_{2}, b_{5})\) are the ten edge disjoint copies of \(4\)-cycles. Required \(6\)-cycle is given by \((a_{1}, b_{2}, c_{3}, a_{3}, b_{4}, c_{4})\). Edge disjoint copies of \(3\)-cycles are same as given above.
(1, 10, 2): Ten copies of \(4\)-cycles are \((a_{1}, b_{1}, c_{3}, b_{3})\), \((a_{1}, c_{1}, a_{2}, c_{5})\), \((a_{2}, b_{1}, c_{5}, b_{3})\), \((a_{1}, b_{4}, c_{5}, b_{5})\), \((a_{3}, b_{1}, c_{4}, b_{4})\), \((a_{1}, b_{2}, a_{2}, c_{4})\), \((a_{3}, c_{4}, b_{2}, c_{3})\), \((b_{1}, c_{1}, b_{2}, c_{2})\), \((b_{3}, c_{1}, b_{5}, c_{4})\) and \((a_{3}, b_{3}, c_{2}, b_{5})\). Two copies of \(6\)-cycles are \((a_{1}, c_{2}, b_{4}, a_{2}, b_{5}, c_{3})\) and \((a_{2}, c_{2}, a_{3}, c_{1}, b_{4}, c_{3})\). Required \(C_{3}\) is \((a_{3}, b_{2}, c_{5})\).
(1, 7, 4): Required copies of \(4\)-cycles are as follows: \((a_{1}, b_{1}, c_{3}, b_{3})\), \((a_{1}, c_{1}, a_{2}, c_{5})\), \((a_{2}, b_{1}, c_{5}, b_{3})\), \((a_{1}, b_{4}, c_{5}, b_{5})\), \((a_{3}, b_{1}, c_{4}, b_{4})\), \((a_{1}, b_{2}, a_{2}, c_{4})\) and \((a_{3}, c_{4}, b_{2}, c_{3})\). Four copies of \(6\)-cycles are \((a_{1}, c_{2}, b_{4}, a_{2}, b_{5}, c_{3})\), \((a_{2}, c_{2}, a_{3}, c_{1}, b_{4}, c_{3})\), \((a_{3}, b_{3}, c_{1}, b_{1}, c_{2}, b_{5})\) and \((b_{2}, c_{1}, b_{5}, c_{4}, b_{3}, c_{2})\). Required \(C_{3}\) is \((a_{3}, b_{2}, c_{5})\).
(1, 4, 6): \((a_{1}, b_{4}, c_{5}, b_{5})\), \((a_{3}, b_{1}, c_{4}, b_{4})\), \((a_{1}, b_{2}, a_{2}, c_{4})\) and \((a_{3}, c_{4}, b_{2}, c_{3})\) gives the required \(4\)-cycles. Edge disjoint copies of \(6\)-cycles are given by \((a_{1}, c_{2}, b_{4}, a_{2}, b_{5}, c_{3})\), \((a_{2}, c_{2}, a_{3}, c_{1}, b_{4}, c_{3})\), \((a_{3}, b_{3}, c_{1}, b_{1}, c_{2}, b_{5})\), \((b_{2}, c_{1}, b_{5}, c_{4}, b_{3}, c_{2})\), \((a_{1}, b_{1}, c_{3}, b_{3}, a_{2}, c_{5})\) and \((a_{1}, c_{1}, a_{2}, b_{1}, c_{5}, b_{3})\). Required \(3\)-cycle is \((a_{3}, b_{2}, c_{5})\).
(1, 1, 8): \((a_{1}, c_{2}, b_{4}, a_{2}, b_{5}, c_{3})\), \((a_{2}, c_{2}, a_{3}, c_{1}, b_{4}, c_{3})\), \((a_{3}, b_{3}, c_{1}, b_{1}, c_{2}, b_{5})\), \((b_{2}, c_{1}, b_{5}, c_{4}, b_{3}, c_{2})\), \((a_{1}, b_{1}, c_{3}, b_{3}, a_{2}, c_{5})\), \((a_{1}, c_{1}, a_{2}, b_{1}, c_{5}, b_{3})\), \((a_{1}, b_{2}, a_{2}, c_{4}, a_{3}, b_{4})\) and \((a_{1}, c_{4}, b_{1}, a_{3}, c_{5}, b_{5})\) are the 8 edge disjoint copies of \(6\)-cycles. Required \(4\)-cycle is given by \((b_{2}, c_{4}, b_{4}, c_{5})\). One copy of \(C_{3}\) is given by \((a_{3}, b_{2}, c_{5})\).
Thus the graph \(K_{3, 5, 5}\) admits a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition for all possible triplets. ◻
Definition 1. [17] In a \(n \times n\) latin square, if each of the \(2 \times 2\) subsquare has entries of the form,
| \(x\) | \(x + 1\) |
| \(x + 1\) | \(x\) |
Next to prove the existence of \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of \(K_{\ell, m, m}\) with \(m – \ell \equiv 2(\)mod\(\ \hspace{0.1cm} 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(p-1) \hspace{0.1cm} 2 \times 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 \times 2\) subsquares of the form \((x)\).
Example 1. Consider the latin square \(L_{5}\).
\(L_{5} =\)
| \(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, \(L_{11}\) using Lemma 11 as given below.
\(L_{11} =\)
| \( 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 \(m – \ell \equiv 2(\)mod\(\ 4)\), there exists a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of \(K_{\ell, m, m}\).
Proof. The proof is splitted into 2 cases.
Case 1. \(\ell\) is odd.
The graph \(K_{\ell, m, m}\) with \(m – \ell \equiv 2(\)mod\(\ 4)\) has \(m^{2} + 2 \ell m\) edges. Let \(m = 2M + 1\) and \(\ell = 2L + 1\). Here, the number of edges is odd and hence \(p \neq 0\). Let us fix one \(C_{3}\) as \((a_{0}, b_{0}, c_{0})\) in all possible decomposition. In order to prove this result, we use the latin square as described in Lemma 11, say \(L_{m}.\) This latin square is of order \(m\), which will be of the form,
Clearly, \(p \leq \ell m\) and equality can be achieved by considering the entries in the first \(\ell\) rows of \(L_{m}\). These \(3\ell m\) 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 \(\ell\) rows correspond to a \(3\)-cycle, \((a_{i}, b_{j}, c_{k})\). Similarly, an entry \(c\) in the cell \((a, b)\) after first \(\ell\) rows correspond to a single edge from partite set \(2\) to partite set \(3\). Now, the entries in the first \(\ell\) rows of the latin square \(L_{m}\) other than row \(0\) and column \(0\) can be partitioned into \(L(M – 1)\) \(2 \times 2\) subsquares of the form \((x)\) as given in Definition 1 together with \(L\) \(2 \times 2\) partial latin square of the form:
| \(2i – 1\) | \(2i\) | |
| \(2i-1\) | \(2i – 1\) | \(0\) |
| \(2i\) | \(0\) | \(2i\) |
Observe that the edges corresponding to each of the \(2 \times 2\) subsquares is isomorphic to \(K_{2, 2, 2}\) which admits a \((C_{3}, C_{4}, C_{6})\)-decomposition by Lemma 2. Now consider each of the \(L\) partial latin squares
| \(2i – 1\) | \(2i\) | |
| \(2i-1\) | \(2i – 1\) | \(0\) |
| \(2i\) | \(0\) | \(2i\) |
together with the corresponding entries of row \(0\) and column \(0\), that is:
| \(0\) | \(2i – 1\) | \(2i\) | |
| 0 | \(2i\) | \( 2i – 1\) | |
| \(2i – 1\) | \(2i\) | \( 2i – 1 \) | \( 0 \) |
| \(2i\) | \(2i – 1\) | \( 0 \) | \( 2i \) |
The corresponding edges induce a graph isomorphic to \(K_{3, 3, 3} – C_{3}\). By Lemma 3, the graph \(K_{3, 3, 3} – C_{3}\) admits a \((C_{3}, C_{4}, C_{6})\)-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 \[\bigcup_{i = \ell + 1}^{m}\{(0, i)\} \bigcup_{i = \ell + 1}^{m} \{(i, 0)\} \bigcup_{i = \ell + 1}^{m} \{(i, 1), (i, 2), …, (i, m)\}.\]
Now consider the edges corresponding to the entries of the cells \[\bigcup_{i = \ell + 1}^{m} \{(0, i)\} \bigcup_{i = \ell + 1}^{m} \{(i, 0)\} \bigcup_{i = \ell + 1}^{m} \{(i, i)\} \bigcup_{i = \ell + 1}^{m}\{(i, i + 1), (i + 1, i)\}.\]
That is, for some \(k\) with \(\ell + 1 \leq k \leq m\), the entries will be of the form:
| \(0\) | \(2k – 1\) | \(2k\) | |
| 0 | \(\mathbf{2k}\) | \(\mathbf{2k – 1}\) | |
| \(2k – 1\) | \(2k\) | \(2k – 1\) | \(0\) |
| \(2k\) | \(2k – 1\) | \(0\) | \(2k\) |
The edges corresponding to the entries given in Table 1 can be either decomposed into three \(4\)-cycles \((a_{0}, b_{2k – 1}, c_{0}, b_{2k})\), \((a_{0}, c_{2k – 1}, b_{2k – 1}, c_{2k})\) and \((b_{0}, c_{2k – 1}, b_{2k}, c_{2k})\) or into two \(6\)-cycles \((a_{0}, c_{2k – 1}, b_{2k – 1}, c_{0}, b_{2k}, c_{2k})\) and \((a_{0}, b_{2k – 1}, c_{2k}, b_{0}, c_{2k – 1}, b_{2k})\).
The remaining edges, corresponding to the last \((m – \ell)\) rows are decomposed into required \((C_{4}, C_{6})\) by grouping three \(2 \times 2\) subsquares(note that each \(2 \times 2\) subsquare corresponds to a \(4\)-cycle) such that these subsquares are from \(4\) columns of \(L_{m}\) and contains four symbols. For example, see Tables 2 and 3.
| 1 | 2 | 3 | 4 |
| \(M – 2\) | \(M – 1\) | \(2M – 1\) | \(2M\) |
| \(M – 1\) | \(M – 2\) | \(2M\) | \(2M – 1\) |
| \(2M – 1\) | \(2M\) | ||
| \(2M\) | \(2M – 1\) |
| 1 | 2 | 3 | 4 |
| \(2M – 5\) | \(2M – 4\) | ||
| \(2M – 4\) | \(2M – 5\) | ||
| \(2M – 5\) | \(2M – 4\) | \(M – 4\) | \(M – 3\) |
| \(2M – 4\) | \(2M – 5\) | \(M – 3\) | \(M – 4\) |
The edges corresponding to the entries as shown in Table 2 can be decomposed into two \(6\)-cycles \((b_{1}, c_{M – 2}, b_{2}, c_{2M – 1}, b_{3}, c_{2M})\) and \((b_{1}, c_{M – 1}, b_{2}, c_{2M}, b_{4}, c_{2M – 1})\). Similarly, the edges corresponding to the entries in Table 3 can be decomposed into two \(6\)-cycles \((b_{1}, c_{2M – 4}, b_{3}, c_{M – 3}, b_{4}, c_{2M – 5})\) and \((b_{2}, c_{2M – 4}, b_{4}, c_{M – 4}, b_{3}, c_{2M – 5})\).
Similarly, the edges corresponding to other groups with the above mentioned condition(4 column and 4 symbols) admits a \((C_{4}, C_{6})\)-decomposition for all admissible pairs.
Now it remains to show that when \(m – \ell \equiv 2(mod \, 4)\), the last \(m – \ell\) rows of \(L_{m}\) are partitioned into any of the form of Table 2 or 3. First, we consider \(M\) is odd. The case when \(m – \ell = 2\) has been dealt in Lemma 9. Consider \(m-\ell=6\), by the construction of the latin square \(L_{m}\), there are \(3(M – 1)\) of \(2 \times 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 – \ell = 6\).
Next, the case \(m – \ell = 10\) is considered. By the construction of the latin square, there are \(5(M – 1)\) 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(M – 1)\) \(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 \(m \equiv 1 \, (mod \, 6)\), then \(q \geq 1\). Similarly, when \(m \equiv 3 \, (mod \, 6)\), then \(q \geq 0\) and when \(m \equiv 5 \, (mod \, 6)\), then \(q \geq 1\). For instance, consider the case \(m – \ell \equiv 3(mod \, 6)\). 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 \((C_{4}, C_{6})\) for all admissible pairs.
A similar approach can be used to partition the last \(10\) rows of \(L_{m}\) in the case \(m \equiv 1(mod \, 6)\) and \(m \equiv 5(mod \, 6)\). Thus, the case \(m – \ell = 10\) is done.
Next, we consider the case \(m – \ell = 14\). These \(14\) rows are made up of \(7(M – 1)\) 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 \(m \equiv 1 \, (mod \, 6)\), then \(q \geq 2\). Similarly, when \(m \equiv 3 \, (mod \, 6)\), then \(q \geq 0\) and when \(m \equiv 5 \, (mod \, 6)\), then \(q \geq 2\). For instance, consider the case \(m – \ell \equiv 3(mod \, 6)\). 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 \((C_{4}, C_{6})\) for all admissible pairs.
The same approach can be used to partition the last \(14\) rows of the latin square in cases when \(m \equiv 1(mod \, 6)\) and \(m \equiv 5(mod \, 6)\).
In the case when \(p = \ell m\), the edges corresponding to the last \(m – \ell\) rows can be decomposed into \((C_{4}, C_{6})\) 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\) | \(2k – 1\) | \(2k\) | |
|---|---|---|---|
| \(2k-1\) | \(2k\) | \(2k-1\) | \(0\) |
| \(2k\) | \(2k-1\) | \(0\) | \(2k\) |
Two such \(6\)-cycles can be decomposed into three \(4\)-cycles as follows. For instance, consider \(m-\ell=6,\) then the last \(6\) rows of the latin square will be of the form; See Table 4.
| 1 | 2 | 3 | 4 | \(\cdots\) | \(2M – 5\) | \(2M – 4\) | \(2M – 3\) | \(2M – 2\) | \(2M – 1\) | \(2M\) | |
| \(2M – 4 \) | \( M – 2 \) | \( M – 1 \) | \( 2M – 1\) | \( 2M\) | \(\cdots\) | \(2M-5\) | \(0\) | \(M – 4\) | \(M – 3\) | \(2M – 3\) | \( 2M – 2\) |
| \(2M – 5\) | \( M – 1 \) | \( M – 2 \) | \(2M\) | \(2M – 1\) | \( \cdots \) | \(0\) | \(2M – 4\) | \(M – 3\) | \(M – 4\) | \(2M – 2\) | \( 2M – 3\) |
| \(2M – 2\) | \(2M – 1\) | \(2M\) | \(2M – 5\) | \(2M – 4\) | \( \cdots \) | \(M – 4\) | \(M – 3\) | \( 2M – 3\) | \(0\) | \(M – 2\) | \(M – 1\) |
| \(2M – 3\) | \(2M\) | \(2M – 1\) | \(2M – 4\) | \(2M – 5\) | \( \cdots \) | \(M – 3\) | \(M – 4\) | \(0\) | \( 2M – 2\) | \(M – 1\) | \(M – 2\) |
| \(2M – 5\) | \(2M – 4\) | \(M – 4\) | \(M – 3\) | \(\cdots\) | \(2M – 3\) | \(2M – 2\) | \(M – 2\) | \(M – 1\) | \(2M-1\) | \(0\) | |
| \(2M – 4\) | \( 2M – 5 \) | \(M – 3\) | \(M – 4\) | \(\cdots\) | \(2M – 2\) | \(2M – 3\) | \(M – 1\) | \(M – 2\) | \(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 \(C_{4},\) given by, \((b_{0}, c_{2M – 5}, b_{2M – 5}, c_{2M – 3})\), \((b_{2M – 2}, c_{0}, b_{2M – 5}, c_{2M – 2})\), \((b_{0}, c_{2M – 4}, b_{2M – 4}, c_{2M – 2})\), \((b_{2M – 4}, c_{M – 4}, b_{2M – 5}, c_{M – 3})\), \((b_{2M – 3}, c_{0}, b_{2M – 4}, c_{2M – 3})\) and \((b_{2M – 2}, c_{M – 4}, b_{2M – 3}, c_{M – 3})\).
It is straightforward to check that similar edge trading is possible to have all possible \((C_{4},\,C_{6})\) corresponding to the edges of the entries in these \((m – \ell)\) rows.
When \(m – \ell > 14\), \(m – \ell = 6x + 10y + 14z\) where \(x, y, z \geq 0\) and the entries in the last \(m – \ell\) rows of the latin square can be partitioned as above and the corresponding edges can be decomposed into \((C_{4}, C_{6})\). Thus, there exists a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of \(K_{\ell, m, m}\) with \(p \leq \ell m\) and \(m – \ell \equiv 2(mod \, 4)\) when \(M\) is odd.
Similarly, when \(M\) is even, the entries in the last \(m – \ell\) rows of the latin square can be grouped using the above mentioned conditions(4 columns and 4 entries).
Thus, there exists a \(\{C_{3}^{p},
C_{4}^{q}, C_{6}^{r}\}\)-decomposition of \(K_{\ell, m, m}\) with \(p \leq \ell m\) and \(m – \ell \equiv 2(mod \, 4)\).
Case 2. \(\ell\) is
even.
In order to prove this case, we consider a latin square of order \(m\),
| \(1\) | \(2\) | \(3\) | \(4\) | \(\cdots\) | \(m – 1\) | \(m\) | |
|---|---|---|---|---|---|---|---|
| \(2\) | \(1\) | \(4\) | \(3\) | \(\cdots\) | \(m\) | \(m – 1\) | |
| \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\cdots\) | \(\vdots\) | \(\vdots\) | |
| \(\ell – 1\) | \(\ell\) | \(\ell + 1\) | \(\ell + 2\) | \(\cdots\) | \(\ell – 2\) | \(\ell – 3\) | |
| \(\ell\) | \(\ell – 1\) | \(\ell + 2\) | \(\ell + 1\) | \(\cdots\) | \(\ell – 3\) | \(\ell – 2\) | |
| \(\ell + 1\) | \(\ell + 2\) | \(\ell + 3\) | \(\ell + 4\) | \(\cdots\) | \(\ell – 1\) | \(\ell\) | |
| \(\ell + 2\) | \(\ell + 1\) | \(\ell + 4\) | \(\ell + 3\) | \(\cdots\) | \(\ell\) | \(\ell – 1\) | |
| \(\ell + 3\) | \(\ell + 4\) | \(\ell + 5\) | \(\ell + 6\) | \(\cdots\) | \(\ell + 1\) | \(\ell + 2\) | |
| \(\ell + 4\) | \(\ell + 3\) | \(\ell + 6\) | \(\ell + 5\) | \(\cdots\) | \(\ell + 2\) | \(\ell + 1\) | |
| \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\cdots\) | \(\vdots\) | \(\vdots\) | |
| \(m – 1\) | \(m\) | \(1\) | \(2\) | \(\cdots\) | \(m – 3\) | \(m – 2\) | |
| \(m\) | \(m – 1\) | \(2\) | \(1\) | \(\cdots\) | \(m – 2\) | \(m – 3\) |
The first \(\ell\) rows of the above latin square can be partitioned into \(2 \times 2\) subsquares each of which correspond to \(K_{2, 2, 2}\). Lemma 2 guarantees the existence of \(3,4\) and \(6\) cycle decomposition of \(K_{2, 2, 2}\) for all admissible triplets. By the structure of the latin square, the edges corresponding to each \(2\times 2\) subsquare in the remaining \((m – \ell)\) rows give rise to \(C_{4}\). 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_{\ell, \, m, \, n}(\ell \leq m \leq n)\), admits a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition.
Proof. The graph \(K_{\ell, m, n} = K_{\ell, m, m} \bigoplus K_{\ell + m, n – m}\). By Lemmas 8, 9, 10, 12, there exists a \(3,4\) and \(6\) cycle decomposition of \(K_{\ell, m, m}\) for all admissible triplets. Theorem 2 assures the existence of \(4\) and \(6\) cycle decomposition of \(K_{\ell + m, n – m}\) for all \(m\) and \(n,\) where \(n – m > 2\). Hence we consider the case \(n – m = 2\) to complete the proof of this theorem.
Case 1. \(m – \ell \equiv 0(mod \, 4)\).
Consider the graph \(K_{\ell, \, m, \, n}\) with \(m – \ell \equiv 0 (mod \, 4)\). In order to prove this result, it is enough to consider the graph \(K_{\ell, \, \ell + 4, \, \ell + 6}\). The graph \(K_{\ell, \, \ell + 4, \, \ell + 6}\) can be represented using a partial latin square of order \(\ell + 6\), as shown in Figure 4.
<The first \(\ell \times (\ell+ 4)\) entries form a latin rectangle. Entries outside the latin rectangle are separated by double line. Each entry of column \(\ell + 5\) and \(\ell + 6\) denote an edge from partite set \(1\) to \(3\). Similarly, each entry of rows \(\ell + 1\) to \(\ell + 6\) denote an edge from partite set \(2\) to \(3\). That is, if the cell \((\ell, \ell + 5)\) contains the entry \(\ell + 5\), then the corresponding edge is \(a_{\ell} c_{\ell + 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 \(C_{4}\) 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 \(C_{4}\). For example, consider the four underlined entries as shown in table below. These entries correspond to a \(C_{4}\) namely \((a_{1}, c_{\ell + 5}, b_{1}, c_{\ell + 6})\) in \(K_{\ell, \, \ell + 4, \, \ell + 6}\).
| \(1\) | \(\ell + 5\) | \(\ell + 6\) | ||
|---|---|---|---|---|
| \(1\) | \(\ell + 5\) | \(\ell + 6\) | ||
| \(\ell + 5\) | \(\ell + 5\) | |||
| \(\ell + 6\) | \(\ell + 6\) |
Construction 2. In this type of construction, we consider only the edges between the partite set \(2\) to \(3\) to construct a \(C_{4}\). For example, consider the four bold entries as shown in the table below. These entries also correspond to a \(C_{4}\) namely, \((b_{1}, c_{\ell + 3}, b_{3}, c_{\ell + 4})\).
| \(1\) | \(3\) | |
|---|---|---|
| \(\ell + 1\) | \(\ell + 3\) | |
| \(\ell + 2\) | \(\ell + 4\) | |
| \(\ell + 3\) | \(\ell + 3\) | |
| \(\ell + 4\) | \(\ell + 4\) |
Thus by using these two types of construction, all the remaining edges can be decomposed into \(4\)-cycles. Thus, we have a \(C_{4}\)-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 \((a_{1}, c_{\ell + 5}, b_{1}, c_{\ell +
6})\), \((a_{2}, c_{\ell + 6}, b_{2},
c_{1})\) and \((b_{2}, c_{\ell + 4},
b_{4}, c_{\ell + 5})\) which can be decomposed into two copies of
\(C_{6}\) \((a_{1}, c_{\ell + 5}, b_{4}, c_{\ell + 4}, b_{2},
c_{\ell + 6})\) and \((a_{2}, c_{1},
b_{2}, c_{\ell + 5}, b_{1}, c_{\ell + 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 \((b_{1}, c_{\ell + 1}, b_{\ell + 3}, c_{\ell +
2})\), \((b_{1}, c_{\ell + 3}, b_{3},
c_{\ell + 4})\) and \((b_{2}, c_{\ell +
2}, b_{\ell + 4}, c_{\ell + 3})\) which can then be decomposed
into 2 copies of \(C_{6}\) given by
\((b_{1}, c_{\ell + 1}, b_{\ell + 3}, c_{\ell
+ 2}, b_{\ell + 4}, c_{\ell + 3})\) and \((b_{1}, c_{\ell + 2}, b_{2}, c_{\ell + 3}, b_{3},
c_{\ell + 4})\).
By using Type 1 and Type 2 edge trading, all the remaining edges can be decomposed into copies of \((C_{4}, C_{6})\).
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_{\ell, \, m, \, n}\) with \(m – \ell \equiv 0(mod \, 4)\) admits a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition.
\(m – \ell = 2 (mod \, 4)\).
In this case, let \(K_{\ell, \, m, \, m + 2} = K_{\ell,\, m, \, m}\bigoplus K_{\ell + m, \, 2}\). By Theorem 2, all the edges corresponding to \(K_{\ell + m, \, 2}\) can be decomposed into edge disjoint copies of \(C_{4}\). In order to obtain cycles of length \(6\), we use edge trading. Let \(\ell\) be even. In order to prove this result, it is enough to consider the graph \(K_{\ell, \, \ell + 2, \ell + 4}\). Then the graph \(K_{\ell, \, \ell + 2, \ell + 2}\) along with the entries corresponding to the bipartite graph \(K_{2\ell + 2, 2}\) can be represented using the partial latin square of order \(\ell + 4\). See Figure 5.
Similar to Case 1, the first \(\ell \times (\ell+ 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 \(\ell + 1\) and \(\ell + 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 \(\frac{\ell + 2}{2}\) \(C_{4}\) from \(K_{\ell, \, \ell + 2, \, \ell + 2}\)(the edges corresponding to the entries in the last 2 rows of the latin square \(K_{\ell, \, \ell + 2, \, \ell + 2}\)) together with the edges of \(K_{2\ell + 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 \(C_{6}\) given by \((b_{1}, c_{\ell + 1}, b_{2}, c_{\ell + 3}, a_{1}, c_{\ell + 4})\). Similarly, the entries in the rectangular box correspond to a \(C_{6}\) given by \((b_{1}, c_{\ell + 2}, b_{2}, c_{\ell + 4}, a_{2}, c_{\ell + 3})\). By proceeding this way, the remaining edges can be decomposed into copies of \(C_{6}\).
When \(\ell\) is odd, the complete tripartite graph \(K_{\ell, \, 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_{\ell, \, m, \, n}(\ell \leq m \leq n)\) can be decomposed into \(p\) copies of \(C_{3}\), \(q\) copies of \(C_{4}\) and \(r\) copies of \(C_{6}\) for all admissible triplets \((p, q, r).\) ◻
Theorem 1. The complete tripartite graph \(K_{\ell, \, m, \, n}(\ell \leq m \leq n)\) admits a \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition if and only if the partite sets are of same parity and \(3p + 4q + 6r = \ell m + mn + \ell n\).
Proof. The proof follows from Lemma 7, Theorem 3, Theorem 4 and Theorem 5. ◻
In this paper, the necessary condition for the existence of \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of complete tripartite graph \(K_{\ell, m, n}(\ell \leq m \leq n)\) has been proved to be sufficient. This answers the problem posted by Billington in the affirmative. The problem of \(\{C_{3}^{p}, C_{4}^{q}, C_{6}^{r}\}\)-decomposition of \(K_{m} \circ \bar{K_{n}}\) is still open for \(m > 3\).
There is no conflict of interest related to this work.