Let \(P_k\) and \(C_k\) respectively denote a path and a cycle on \(k\) vertices. In this paper, we give necessary and sufficient conditions for the existence of a complete \(\left\{P_7,C_6\right\}\)-decomposition of the cartesian product of complete graphs.
Unless stated otherwise all graphs considered here are finite, simple, and undirected. For the standard graph-theoretic terminology the readers are referred to [5]. Let \(P_k,\ C_k,\ S_k,\ K_k\) respectively denote a path, cycle, star and complete graph on \(k\) vertices, and let \(K_{m,n}\) denote the complete bipartite graph with \(m\) and \(n\) vertices in the parts. A graph whose vertex set is partitioned into subsets \(V_1, . . . , V_m\) such that the edge set is \(\cup_{i\neq j\in[m]} V_i \times V_j\) is a complete \(m\)-partite graph, denoted as \(K_{n_1,…,n_m}\) , when \(\left|V_i\right| = n_i\) for all \(i\). For \(G = K_{2n}\) or \(K_{n,n}\), the graph \(G – I\) denotes the graph G with a \(1\)-factor \(I\) removed. For any integer \(\lambda > 0\), \(\lambda G\) denotes \(\lambda\) edge-disjoint copies of \(G\). The complement of the graph \(G\) is denoted by \(\overline{G}\). For two graphs \(G\) and \(H\) we define their \(Cartesian\) \(product\), denoted by \(G \Box H\), as follows: the vertex set is \(V(G) \times V(H)\) and its edge set is
\[E(G \Box H)=\left\{(g, h)(g', h') : g = g',\ hh' \in E(H),\ or \ gg' \in E(G),\ h = h'\right\}.\]
It is well known that the Cartesian product is commutative and associative. For a graph \(G\), a partition of \(G\) into edge-disjoint sub graphs \(H_1,\cdots , H_k\) such that \(E(G) = E(H_1)\cup \cdots \cup E(H_k)\) is called a decomposition of \(G\) and we write \(G\) as \(G=H_1\oplus \cdot\cdot\cdot \oplus H_k\). For \(1\leq i\leq k\), if \(H_i\cong H\), we say that \(G\) has a \(H\)-decomposition. If \(G\) has a decomposition into \(p\) copies of \(H_1\) and \(q\) copies of \(H_2\), then we say that \(G\) has a \(\left\{pH_1,qH_2\right\}\)-decomposition. If such a decomposition exists for all possible values of \(p\) and \(q\) satisfying trivial necessary conditions, then we say that \(G\) has a \(\left\{H_1, H_2\right\}_{\left\{p,q\right\}}\)-decomposition or complete \(\left\{H_1, H_2\right\}\)-decomposition.
The study of \(\left\{H_1, H_2\right\}_{\left\{p,q\right\}}\)-decomposition of graphs is not new. Authors in [2,4] completely determined the values of \(n\) for which \(K_n(\lambda)\) admits a \(\left\{pH_1,qH_2 \right\}\)-decomposition such that \(H_1\cup H_2\cong K_t\), when \(\lambda \geq 1\) and \(\left|V(H_1)\right| = \left|V(H_2)\right| = t\), when \(t\in \left\{4, 5\right\}\). Abueida and Daven [3] proved that there exists a \(\left\{pK_k , qS_{k+1}\right\}\)-decomposition of \(K_n\), for \(k\geq 3\) and \(n\equiv 0, 1 (mod\ k)\). Abueida and O’Neil [1] proved that for \(k\in \left\{3, 4, 5\right\}\), there exists a \(\left\{pC_k , qS_k\right\}\)-decomposition of \(K_n(\lambda)\), whenever \(n\geq k+1\) except for the ordered triples \((k, n, \lambda)\in \{(3, 4, 1)\), \((4, 5, 1)\), \((5,6, 1)\), \((5, 6, 2)\), \((5, 6, 4)\), \((5, 7, 1)\), \((5, 8, 1)\}\). Farrell and Pike [7] shown that the necessary conditions are sufficient for the existence of \(C_6\)-decomposition of \(K_{m} \Box K_{n}\). Fu et al. [8] established necessary and sufficient condition for the existence of \(\left\{C_3 , S_{4}\right\}_{\left\{p,q\right\}}\)-decomposition of \(K_n\). Shyu [12] obtained a necessary and sufficient condition on \(\left\{p, q\right\}\) for the existence of \(\left\{P_5,C_4\right\}_{\left\{p,q\right\}}\)-decomposition of \(K_n\). Priyadharsini and Muthusamy [11] established necessary and sufficient condition for the existence of the \(\{pG_n, qH_n\}\)-decomposition of \(K_n(\lambda)\) when \(G_n, H_n\in \left\{C_n, P_{n-1}, S_{n-1}\right\}\). Jeevadoss and Muthusamy [9] obtained some necessary and sufficient conditions for the existence of \(\left\{P_{k+1},C_k\right\}_{\left\{p,q\right\}}\)-decomposition of \(K_{m,n}\). Jeevadoss and Muthusamy [10] obtained necessary and sufficient conditions for the existence of \(\left\{P_5,C_4\right\}_{\left\{p,q\right\}}\)-decomposition of \(K_m \times K_n\), \(K_m\otimes \overline{K_n}\) and \(K_m\Box K_n\). Pauline Ezhilarasi and Muthusamy [6] have obtained necessary and sufficient conditions for the existence of a decomposition of product graphs into paths and stars with three edges.
In this paper, we show that the necessary condition \(mn(m+n-2) \equiv\,0\,\pmod {12}\) is sufficient for the existence of a \(\left\{P_7,C_6\right\}_{\{p,q\}}\)-decomposition of \(K_{m} \Box K_{n}\). We abbreviate the \(\left\{P_{k+1},C_k\right\}_{\{p,q\}}\)-decomposition as \((k;p,q)\)-decomposition.
To prove our results we state the following:
Theorem 1.1 ([9]). Let \(p\), \(q\) be non-negative integers, \(k\) be an even integer and \(n>4k\) be an odd integer. If \(k(p+q)={n \choose 2}\) and \(p\neq 1\), then \(K_n\) has a \((k;p,q)\)-decomposition.
Theorem 1.2 [9]. Let \(s,t>0\) be integers and \(k\geq 4\) be an even integer. Then the graph \(K_{sk,tk}\) has a \((k;p,q)\)-decomposition.
Remark 1.3. If \(G\) and \(H\) have a \((6;p,q)\)-decomposition, then \(G \cup H\) has a such decomposition. In this paper, we denote \(G \cup H\) as \(G \oplus H\).
Construction 1.4. Let \(C_6^1\) and \(C_6^2\) be two cycles of length 6, where \(C_6^1 = (x_0x_1x_2x_3x_4x_5x_0)\) and \(C_6^2 = (y_0 y_1 y_2 y_3 y_4y_5y_0)\). If \(v\) is a common vertex of \(C_6^1\) and \(C_6^2\) such that at least one neighbour of \(v\) from each cycle (say, \(x_i\) and \(y_j\)) does not belong to the other cycle then we have two edge-disjoint paths of length 6, say \(P_7^1\) and \(P_7^2\) from \(C_6^1\) and \(C_6^2\) as follows:
\[P_7^1=(C_6^1-vx_i)\cup vy_j,\] and \[P_7^2=(C_6^2 – vy_j)\cup vx_i.\]
In this section we prove some basic lemmas which are used to prove our results. Throughout this paper, we denote \(V(K_n) = \{x_i : 1\leq i\leq n\}\).
Lemma 2.1. There exists a \((6;p,q)\)-decomposition of \(K_7\backslash E(K_3)\), \(p\neq 1\).
Proof. First we decompose \(K_7 \backslash E(K_3)\) into 3\(C_6\) as follows:
\[\{(x_2\mathbf{x_5x_1x_4x_3x_6x_2}), \,(x_2x_4x_6x_1x_3\mathbf{x_7x_2}),\, (x_1x_2x_3x_5x_6x_7x_1)\}.\]
The bold edges (resp., ordinary edges) gives 2\(P_7\) from first two cycles. Now, the 3\(P_7\) are \[\{x_4x_6x_7x_1x_2x_3x_5,x_7x_3x_6x_1x_4x_2x_5,x_7x_2x_6x_5x_1x_3x_4\}.\]
Hence \(K_7\backslash E(K_3)\) has a \((6;p,q)\)-decomposition. ◻
Lemma 2.2. There exists a \((6;p,q)\)-decomposition of \(K_{8}-I\), \(p\neq 1\).
Proof. First we decompose \(K_8-I\) into \(C_6\)’s as follows: \[\{(x_1\mathbf{x_5x_8x_2x_6x_7x_1}),(\mathbf{x_1x_3}x_2x_7x_4x_8x_1)\},\{(x_5\mathbf{x_7x_3x_8x_6x_4x_5}),(\mathbf{x_5x_2}x_4x_1x_6x_3x_5)\}.\]
The last 3\(C_6\) can be decomposed into 3\(P_7\) as follows: \[\{x_5x_8x_2x_6x_7x_1x_3,x_3x_2x_7x_5x_4x_8x_6,x_6x_4x_7x_3x_8x_1x_5\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)-decomposition given above. ◻
Lemma 2.3. There exists a \((6;p,q)\)-decomposition of \(K_9\), \(p\neq 1\).
Proof. First we decompose \(K_9\) into \(C_6\)’s as follows: \[\begin{aligned} &\{(x_1\mathbf{x_3x_5x_7x_9x_2x_1}),(\mathbf{x_1x_4}x_6x_8x_2x_5x_1)\},\{(x_1\mathbf{x_6x_2x_3x_4x_7x_1}),\\&(\mathbf{x_1x_8}x_3x_7x_6x_9x_1)\}, \{(x_4\mathbf{x_5x_6x_3x_9x_8x_4}),(\mathbf{x_4x_2}x_7x_8x_5x_9x_4)\}.\end{aligned}\]
The last 3\(C_6\) can be decomposed into 3\(P_7\) as follows: \[\{x_1x_8x_3x_7x_6x_9x_5,x_5x_8x_7x_2x_4x_9x_3,x_3x_6x_5x_4x_8x_9x_1\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)-decomposition given above. ◻
Lemma 2.4. There exists a \((6;p,q)\)-decomposition of \(K_{6k,4l}\), \(k,l\in \mathbb{Z}^+\) and \(p\neq 1\).
Proof. Let \(V(K_{6,4})=\left\{x_1,\cdots ,x_6\right\}\cup \left\{y_1,\cdots ,y_4\right\}\). First we decompose \(K_{6,4}\) into \(C_6\)’s as follows: \[\{(y_2\mathbf{x_2y_3x_3y_1x_1y_2}),(\mathbf{y_2x_5}y_3x_6y_4x_4y_2)\},\{(\mathbf{y_1x_2}y_4x_1y_3x_4y_1), (y_1\mathbf{x_5y_4x_3y_2x_6y_1})\}.\]
From the first 3\(C_6\) we can find 3\(P_7\) as follows: \[\{y_1x_1y_3x_4y_2x_5y_3,y_3x_6y_4x_4y_1x_2y_4,y_4x_1y_2x_2y_3x_3y_1\}.\]
Now, using Construction 1.4 we get a required number of paths and cycles from the \(C_6\)-decomposition given above. Hence \(K_{6,4}\) has a \((6;p,q)\)-decomposition. Now, we can write \(K_{6k,4l}=klK_{6,4}\). Hence by Remark 1.3, \(K_{6k,4l}\) has a \((6;p,q)\)-decomposition. ◻
Lemma 2.5. There exists a \((6;p,q)\)-decomposition of
(i). \(K_{12l+1}\backslash E(2lC_6)\) with \(p\neq 1\) and
(ii). \(K_{12k}\backslash E(2kC_6)\) with \(p\geq 6k\), where \(2lC_6\) and \(2kC_6\) are vertex disjoint cycles and \(k,l\in \mathbb{Z}^+\).
Proof. (i). Let \[\begin{aligned}&\{\{(x_1\mathbf{x_4x_2x_6x_3x_5x_1}),
(\mathbf{x_1x_{10}}x_4x_7x_2x_{12}x_1)\},
\{(x_7\mathbf{x_{13}x_{10}x_{12}x_8x_{11}x_7}),
(\mathbf{x_7x_9}x_{12}x_{13}x_8x_{10}x_7)\},\\&
\{(x_8\mathbf{x_2x_{10}x_3x_7x_1x_8}),
(\mathbf{x_8x_5}x_{10}x_6x_{12}x_4x_8)\},
\{(x_9\mathbf{x_1x_3x_{13}x_{11}x_2x_9}),
(\mathbf{x_9x_4}x_{13}x_5x_{11}x_6x_9)\},\\&
\{(x_9x_{11}\mathbf{x_1x_{13}x_2x_5x_9}),
(x_9x_3x_{11}x_4\mathbf{x_6x_{13}x_9})\},
(x_3x_8x_6x_7x_5x_{12}x_3)\},\end{aligned}\] be the \(C_6\)-decomposition of \(K_{13}\backslash E(2C_6)\), where 2\(C_6\) removed from \(K_{13}\) are given by \((x_1x_2x_3x_4x_5x_6x_1)\),
\((x_7x_8x_9x_{10}x_{11}x_{12}x_7)\).
The last 3\(C_6\) can be decomposed
into 3\(P_7\) as follows: \[\{x_{12}x_3x_9x_{13}x_6x_4x_{11},
x_3x_8x_6x_7x_5x_9x_{11}, x_3x_{11}x_1x_{13}x_2x_5x_{12}\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)-decomposition given above. Hence \(K_{13}\backslash E(2C_6)\) has a \((6;p,q)\)-decomposition, where the \(2C_6\) removed from \(K_{13}\) are vertex disjoint cycles. We can write \(K_{12l+1} = K_{12(l-1)+1}\ \oplus\ K_{13}\ \oplus\ K_{12(l-1),12}\). Applying this relation recursively to \(K_{12(l-1)+1}\) and using Theorem 1.2, we can have a \((6;p,q)\)-decomposition of \(K_{12l+1} \backslash E(2lC_6)\), where the \(2lC_6\) removed from \(K_{12l+1}\) are vertex disjoint cycles.
(ii). Since the degree of each vertex \(v\in V(K_{12k}\backslash E(2kC_6))\) is
odd, then \(p\geq 6k\). Let \[\begin{aligned}&\{x_{1}x_{12}x_{2}x_{11}x_{3}x_{10}x_{4}, x_{3}x_{9}x_{4}x_{8}x_{5}x_{7}x_{6},
x_{2}x_{4}x_{6}x_{8}x_{10}x_{1}x_{5},
x_{7}x_{9}x_{12}x_{3}x_{6}x_{2}x_{10},
x_{9}x_{11}x_{1}x_{3}x_{5}x_{10}x_{12},\\&x_{11}x_{4}x_{7}x_{10}x_{6}x_{12}x_{8},
\{(x_{1}\mathbf{x_{8}x_{3}x_{7}x_{2}x_{9}x_{1}}),
(x_{1}x_{7}x_{11}x_{5}x_{12}\mathbf{x_{4}x_{1}})\},
(x_{2}x_{5}x_{9}x_{6}x_{11}x_{8}x_{2})\},\end{aligned}\] be the
\(\left\{6P_7,\
3C_6\right\}\)-decomposition of \(K_{12}\backslash E(2C_6)\), where the
2\(C_6\) removed from \(K_{12}\) are
\((x_1x_2x_3x_4x_5x_6x_1)\), \((x_7x_8x_9x_{10}x_{11}x_{12}x_7)\). For
\(p=7\), we decompose the last cycle
and the first path into 2\(P_7\) as
follows: \[\{x_{1}x_{12}x_{2}x_{11}x_6x_9x_5,
x_5x_2x_8x_{11}x_{3}x_{10}x_{4}\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the decomposition given above. Hence \(K_{12}\backslash E(2C_6)\) has a \((6;p,q)\)-decomposition, where the \(2C_6\) removed from \(K_{12}\) are vertex disjoint cycles. We can write \(K_{12k} = K_{12(k-1)}\oplus K_{12}\oplus K_{12(k-1),12}\). Applying this relation recursively to \(K_{12(k-1)}\) and using Theorem 1.2, we can have a \((6;p,q)\)-decomposition of \(K_{12k} \backslash E(2kC_6)\), where \(2kC_6\) removed from \(K_{12k}\) are vertex disjoint cycles. ◻
Lemma 2.6. There exists a \((6;p,q)\)-decomposition of \(K_m\backslash E(K_3), m\equiv\,3,\ 7\,\pmod {12}\), \(m>3\) and \(p\neq 1\).
Proof. Let \(m=12k+i\),
where \(i=3,7\). We prove it in two
cases.
Case 1. \(m = 12k+3\). When \(m=15\), \(K_{15}\backslash E(K_3)=K_9\ \oplus\ (K_7 \backslash E(K_3))\ \oplus\ K_{8,6}\). By Lemmas 2.1, 2.3 and 2.4 and Remark 1.3, \(K_{15}\backslash E(K_3)\) has a \((6;p,q)\)-decomposition. For \(m > 15\), we can write \(K_m\backslash E(K_3)=K_{12(k-1)+1}\) \(\oplus\ (K_{15} \backslash E(K_3))\ \oplus\ K_{12(k-1),14}=K_{12(k-1)+1}\ \oplus\ (K_{15} \backslash E(K_3))\ \oplus\ K_{12(k-1),6}\) \(\oplus\ K_{12(k-1),8}\). By Theorems 1.1, 1.2, Lemma 2.1 and Remark 1.3, \(K_m\backslash E(K_3)\) has a \((6;p,q)\)-decomposition.
Case 2. \(m = 12k+7\). We can write \(K_m\backslash E(K_3)=K_{12k+1}\ \oplus\ (K_7 \backslash E(K_3))\) \(\oplus\ K_{12k,6}\). By Theorems 1.1, 1.2, Lemma 2.1 and Remark 1.3, \(K_m\backslash E(K_3)\) has a \((6;p,q)\)-decomposition.
Lemma 2.7. There exists a \((6;p,q)\)-decomposition of \(K_m\backslash E(C_4)\) for \(m\equiv\,5\,\pmod {12}\) and \(K_m\backslash E(C_7)\) for \(m\equiv\,11\,\pmod {12}\).
Proof.
Case 1. \(m\equiv\,5\,\pmod {12}\). When \(m=17\), \(K_{17}\backslash E(C_4)=K_8\ \oplus\ K_9\ \oplus\ (K_{8,9}\backslash E(C_4))\). Let \(V_1=V(K_8)=\left\{x_i : 1\leq i\leq 8\right\}\) and \(V_2=V(K_9)=\left\{y_i : 1\leq i\leq 9\right\}\). So, \(V(K_{8,9})=V_1\cup V_2\). Let \[\begin{aligned}&\{(x_1\mathbf{y_2x_2y_4x_3y_5x_1}), (\mathbf{x_1y_1}x_3x_4y_3x_2x_1)\}, \{(x_5\mathbf{y_7x_2y_6x_4y_9x_5}), (\mathbf{x_5x_6}y_8x_7x_8y_6x_5)\},\\& \{(x_6x_8x_4x_1x_7\mathbf{x_2x_6}), (x_6\mathbf{x_3x_1x_8x_5x_4x_6})\}, \{(y_8\mathbf{x_2y_9x_6y_4x_1y_8}), (\mathbf{y_8x_5}y_1x_7y_6x_3y_8)\}, \\&\{(x_8\mathbf{y_7x_6y_5x_2y_1x_8}),(\mathbf{x_8y_8}x_4y_7x_7y_9x_8)\}, \{(y_3\mathbf{x_3y_2x_6y_6x_1y_3}), (\mathbf{y_3x_7}y_4x_4y_5x_5y_3)\}, \\&\{(x_2x_5x_1\mathbf{x_6x_7}x_3x_2), (\mathbf{x_4x_2x_8x_3x_5x_7}x_4)\}, \{(x_8\mathbf{y_5x_7y_2x_5y_4x_8}),(\mathbf{x_8y_3}x_6y_1x_4y_2x_8)\},\end{aligned}\] be the \(C_6\)-decomposition of \(K_8\ \oplus\ (K_{8,9}\backslash E(C_4))\). The first 3\(C_6\) can be decomposed into 3\(P_7\) as follows: \[\{x_5y_7x_2y_6x_4x_3y_1, y_2x_2y_4x_3y_5x_1y_1, x_5y_9x_4y_3x_2x_1y_2\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)-decomposition of \(K_8 \oplus (K_{8,9}\backslash E(C_4))\) given above. Hence by Lemma 2.3 and Remark 1.3, \(K_{17}\backslash E(C_4)\) has a \((6;p,q)\)-decomposition. When \(m > 17\), we can write \(K_m\backslash E(C_4)=K_{12k+5}\backslash E(C_4)=K_{12(k-1)+1}\ \oplus\ (K_{17}\backslash E(C_4))\ \oplus\ K_{12(k-1),16}\). By Theorem 1.1 and Lemma 2.4, \(K_{12(k-1)+1}\) and \(K_{12(k-1),16}\) have a \((6;p,q)\)-decomposition. Hence by Remark 1.3, \(K_m\backslash E(C_4)\) has a \((6;p,q)\)-decomposition.
Case 2. \(m\equiv\,11\,\pmod {12}\). We can write \(K_m\backslash E(C_7)=K_{12l+11}\backslash E(C_7)=K_{12l+1}\ \oplus\ K_{12l,10}\ \oplus\ (K_{11}\backslash E(C_7))\) and \(K_{12l,10}=K_{12l,6}\ \oplus\ 2lK_{6,4}\). Let \[\begin{aligned}&\{(x_1\mathbf{x_4x_{10}x_5x_7x_{11}x_1}), (\mathbf{x_1x_8}x_5x_{11}x_{10}x_3x_1)\}, \{(x_2\mathbf{x_7x_3x_9x_6x_8x_2}), (\mathbf{x_2x_{11}}x_3x_5x_1x_{10}x_2)\}, \\&\{(x_9\mathbf{x_4x_{11}x_6x_{10}x_7x_9}), (\mathbf{x_9x_1}x_6x_4x_8x_{10}x_9)\}, \{(x_9\mathbf{x_8x_3x_6x_2x_5x_9}), (\mathbf{x_9x_{11}}x_8x_7x_4x_2x_9)\}, \end{aligned}\] be the \(C_6\)-decomposition of \(K_{11}\backslash E(C_7)\). The first 3\(C_6\) can be decomposed into 3\(P_7\) as follows: \[\{(x_1x_{11}x_4x_3x_7x_2x_8, x_8x_1x_4x_{10}x_5x_{11}x_7, x_1x_3x_9x_6x_8x_5x_7\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)-decomposition given above for \(K_{11}\backslash E(C_7)\). By Theorems 1.1, 1.2, Lemma 2.4 and Remark 1.3, \(K_m\backslash E(C_7)\) has a \((6;p,q)\)-decomposition. ◻
2.8. There exists a \((6;p,q)\)-decomposition of \(K_{m}\), where \(m\equiv\,0,\ 4\,\pmod {12}\) and \(p\geq m/2\).
Proof. Since the degree of each vertex \(v\in V(K_m)\) is odd, then \(p\geq m/2\). We prove the required
decomposition in two Cases.
Case 1. \(m\equiv\,0\,\pmod {12}\). Let \(m=12k\) and \[\begin{aligned}&\{x_{3}x_{9}x_{4}x_{8}x_{5}x_{7}x_{6}, x_{1}x_{12}x_{2}x_{11}x_{3}x_{10}x_{4}, x_{2}x_{4}x_{6}x_{8}x_{10}x_{1}x_{5}, x_{7}x_{9}x_{12}x_{3}x_{6}x_{2}x_{10},x_{9}x_{11}x_{1}x_{3}x_{5}x_{10}x_{12}, \\ &x_{11}x_{4}x_{7}x_{10}x_{6}x_{12}x_{8}, \{(x_{1}\mathbf{x_{8}x_{3}x_{7}x_{2}x_{9}x_{1}}), (x_{1}x_{7}x_{11}x_{5}x_{12}\mathbf{x_{4}x_{1}})\}, \{(\mathbf{x_{2}x_{5}x_{9}x_{6}x_{11}x_{8}}x_{2}), \\ & (\mathbf{x_2x_3}x_4x_5x_6x_1x_2)\}, (x_7x_8x_9x_{10}x_{11}x_{12}x_7)\},\end{aligned}\] be a \(\left\{6P_7,\ 5C_6\right\}\)-decomposition of \(K_{12}\). For \(p=7\), we decompose the last cycle and first path into \(2P_7\) as follows: \[\{x_{3}x_{9}x_{4}x_{8}x_{5}x_{7}x_{12}, x_{6}x_7x_8x_9x_{10}x_{11}x_{12}\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)’s given above for \(p\geq 8\). When \(k>1\), \(K_{12k}=K_{12(k-1)}\ \oplus\ K_{12}\ \oplus\ K_{12(k-1),12}\). Applying this relation recursively to \(K_{12(k-1)}\) and using Theorem 1.2, we can prove that \(K_{12k}\) has a \((6;p,q)\)-decomposition.
Case 2. \(m\equiv\,4\,\pmod {12}\). Let \(m=12k+4\) and
\[\begin{aligned}&\{x_1x_5x_7x_4x_6x_8x_2, x_3x_6x_7x_2x_5x_8x_4, x_5x_3x_7x_8x_1x_2x_6, x_7x_1x_6x_5x_4x_3x_8,x_{14}x_{13}x_{15}x_{12}x_{9}x_{11}x_{10}, \\&x_{16}x_{9}x_{15}x_{10}x_{13}x_{11}x_{12}, x_{13}x_{16}x_{15}x_{11}x_{14}x_{10}x_{9}, x_{15}x_{14}x_{9}x_{13}x_{12}x_{16}x_{11}\}, \end{aligned}\] \[\begin{aligned}&\{(x_{3}\mathbf{x_{9}x_{5}x_{11}x_{2}x_{10}x_{3}}), (\mathbf{x_{3}x_{12}}x_{5}x_{10}x_{4}x_{11}x_{3})\}, \\ &\{(x_{9}\mathbf{x_{2}x_{12}x_{1}x_{15}x_{8}x_{9}}), (\mathbf{x_{9}x_{4}}x_{16}x_{6}x_{13}x_{7}x_{9})\},\\ &\{(x_{13}\mathbf{x_{3}x_{15}x_{5}x_{16}x_{2}x_{13}}), (\mathbf{x_{13}x_{4}}x_{15}x_{7}x_{11}x_{1}x_{13})\},\\ &\{(x_{8}\mathbf{x_{12}x_{7}x_{14}x_{5}x_{13}x_{8}}), (\mathbf{x_{8}x_{11}}x_{6}x_{9}x_{1}x_{10}x_{8})\},\\ &\{(x_{14}\mathbf{x_{6}x_{10}x_{7}x_{16}x_{8}x_{14}}),(\mathbf{x_{14}x_{2}}x_{15}x_{6}x_{12}x_{4}x_{14})\},\\ &\{(x_1x_3x_{14}x_{12}\mathbf{x_{10}x_{16}x_{1}}), (\mathbf{x_1x_{14}x_{16}x_3x_2}x_{4}x_{1})\}\end{aligned}\] be a \(\left\{8P_7,\ 12C_6\right\}\)-decomposition of \(K_{16}\).
For \(p=9\), we decompose the last cycle and last path into \(2P_7\) as follows: \[\{x_{15}x_{14}x_{9}x_{13}x_{12}x_{16}x_3, x_3x_2x_{4}x_{1}x_{14}x_{16}x_{11}\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)’s given above for \(p\geq 10\). When \(k>1\), \(K_{12k+4}=K_{12(k-1)}\ \oplus\ K_{16}\ \oplus\ K_{12(k-1),16}\). By Lemma 2.4 and by applying Case 1, \(K_{12k+4}\) has a \((6;p,q)\)-decomposition. ◻
In this section we investigate the existence of \((6;p,q)\)-decomposition of Cartesian product of complete graphs. Throughout this paper, we denote \(V(K_m \Box K_n) = \left\{x_{i,j} : 1\leq i \leq m, 1\leq j \leq n \right\}\).
Lemma 3.1. There exists a \((6;p,q)\)-decomposition of \(K_3 \Box K_3\), \(p\neq 1\).
Proof. First we decompose \(K_3
\Box K_3\) into \(C_6\)’s as
follows:
\[\{(x_{1,1}\mathbf{x_{1,2}x_{3,2}x_{3,3}x_{2,3}x_{1,3}x_{1,1}}),
(\mathbf{x_{1,1}x_{2,1}}x_{2,3}x_{2,2}x_{3,2}x_{3,1}x_{1,1}),
(x_{1,2}x_{1,3}x_{3,3}x_{3,1}x_{2,1}x_{2,2}x_{1,2})\}.\]
The bold edges (resp., ordinary edges) gives 2\(P_7\) from first two cycles. Also, we can decompose the given graph into \(3P_7\) as follows: \[\{x_{1,2}x_{1,3}x_{3,3}x_{3,2}x_{3,1}x_{1,1}x_{2,1},x_{2,1}x_{2,2}x_{1,2}x_{1,1}x_{1,3}x_{2,3}x_{3,3},x_{3,3}x_{3,1}x_{2,1}x_{2,3}x_{2,2}x_{3,2}x_{1,2}\}.\] Hence \(K_3 \Box K_3\) has a \((6;p,q)\)-decomposition. ◻
Lemma 3.2. There exists a \((6;p,q)\)-decomposition of \(K_3 \Box K_{7}\), \(p\neq 1\).
Proof. First we decompose \(K_3 \Box K_7\) into \(C_6\)’s as follows:
\(\left\{(x_{1,6}\mathbf{x_{2,6}x_{3,6}x_{3,5}x_{1,5}x_{1,2}x_{1,6}}),\
(x_{1,6}x_{3,6}x_{3,4}x_{2,4}x_{1,4}\mathbf{x_{1,3}x_{1,6}})\right\}\),
\(\left\{(x_{1,7}\mathbf{x_{3,7}x_{3,3}x_{3,5}x_{2,5}x_{1,5}x_{1,7}}),\
(\mathbf{x_{1,7}x_{2,7}}x_{3,7}x_{3,1}x_{3,4}x_{1,4}x_{1,7})\right\}\),
\(\left\{(\mathbf{x_{1,7}x_{1,1}x_{1,4}x_{1,6}x_{1,5}x_{1,3}}x_{1,7}),\
(x_{1,7}x_{1,6}x_{1,1}x_{1,5}x_{1,4}\mathbf{x_{1,2}x_{1,7}})\right\}\),
\(\left\{(\mathbf{x_{2,7}x_{2,6}x_{2,1}x_{2,4}x_{2,5}x_{2,3}}x_{2,7}),\
(\mathbf{x_{2,7}x_{2,2}}x_{2,4}x_{2,6}x_{2,5}x_{2,1}x_{2,7})\right\}\),
\(\left\{(x_{3,7}\mathbf{x_{3,2}x_{3,6}x_{3,3}x_{3,4}x_{3,5}x_{3,7}}),\
(\mathbf{x_{3,7}x_{3,6}}x_{3,1}x_{3,5}x_{3,2}x_{3,4}x_{3,7})\right\}\),
\(\left\{(x_{1,3}\mathbf{x_{3,3}x_{3,1}x_{2,1}x_{2,2}x_{1,2}x_{1,3}}),\
(\mathbf{x_{1,3}x_{2,3}}x_{3,3}x_{3,2}x_{1,2}x_{1,1}x_{1,3})\right\}\),
\(\left\{(x_{2,2}\mathbf{x_{2,6}x_{2,3}x_{2,4}x_{2,7}x_{2,5}x_{2,2}}),\
(\mathbf{x_{2,2}x_{3,2}}x_{3,1}x_{1,1}x_{2,1}x_{2,3}x_{2,2})\right\}\).
The first 3\(C_6\) can be decomposed into 3\(P_7\) as follows: \[\{x_{1,3}x_{1,6}x_{3,6}x_{3,5}x_{2,5}x_{1,5}x_{1,7},x_{1,7}x_{3,7}x_{3,3}x_{3,5}x_{1,5}x_{1,2}x_{1,6},x_{1,6}x_{2,6}x_{3,6}x_{3,4}x_{2,4}x_{1,4}x_{1,3}\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)-decomposition given above. ◻
Lemma 3.3. There exists a \((6;p,q)\)-decomposition of \(K_3 \Box K_{8}\), \(p\geq 12\).
Proof. Since the degree of each vertex \(v\in V(K_3 \Box K_8)\) is odd, then \(p\geq \frac{24}{2}=12\). For \(p=12\), the required number of \(P_7\)’s and \(C_6\)’s are constructed as follows:
\(x_{1,1}x_{1,4}x_{2,4}x_{3,4}x_{3,8}x_{3,7}x_{3,5}\),
\(x_{1,2}x_{1,1}x_{1,5}x_{1,8}x_{1,3}x_{3,3}x_{2,3}\),
\(x_{1,3}x_{2,3}x_{2,4}x_{2,6}x_{2,7}x_{2,1}x_{2,5}\),
\(x_{1,4}x_{1,3}x_{1,6}x_{1,5}x_{1,7}x_{3,7}x_{2,7}\),
\(x_{1,5}x_{1,3}x_{1,1}x_{1,7}x_{1,8}x_{3,8}x_{2,8}\),
\(x_{1,6}x_{1,7}x_{1,2}x_{1,4}x_{3,4}x_{3,1}x_{3,8}\),
\(x_{1,7}x_{2,7}x_{2,5}x_{2,3}x_{2,2}x_{2,8}x_{1,8}\),
\(x_{2,1}x_{1,1}x_{3,1}x_{3,3}x_{3,4}x_{3,2}x_{3,7}\),
\(x_{2,2}x_{1,2}x_{3,2}x_{3,1}x_{3,6}x_{3,5}x_{3,3}\),
\(x_{2,4}x_{2,1}x_{2,2}x_{2,7}x_{2,8}x_{2,6}x_{3,6}\),
\(x_{2,6}x_{2,3}x_{2,8}x_{2,5}x_{1,5}x_{3,5}x_{3,4}\),
\(x_{3,1}x_{2,1}x_{2,3}x_{2,7}x_{2,4}x_{2,2}x_{3,2}\),
\(\left\{(\mathbf{x_{1,2}x_{1,5}}x_{1,4}x_{1,8}x_{1,1}x_{1,6}x_{1,2}),\
(x_{1,2}\mathbf{x_{1,3}x_{1,7}x_{1,4}x_{1,6}x_{1,8}x_{1,2}})\right\}\),
\(\left\{(x_{2,6}\mathbf{x_{1,6}x_{3,6}x_{3,2}x_{3,5}x_{2,5}x_{2,6}}),\
(\mathbf{x_{2,6}x_{2,2}}x_{2,5}x_{2,4}x_{2,8}x_{2,1}x_{2,6})\right\}\),
\(\left\{(x_{3,3}\mathbf{x_{3,6}x_{3,7}x_{3,1}x_{3,5}x_{3,8}x_{3,3}}),\
(x_{3,3}x_{3,7}x_{3,4}x_{3,6}x_{3,8}\mathbf{x_{3,2}x_{3,3}})\right\}\).
For \(p=13\), we decompose the last path and the first cycle into 2\(P_7\) as follows: \[\{x_{2,6}x_{2,3}x_{2,8}x_{2,5}x_{1,5}x_{1,4}x_{1,8},x_{1,8}x_{1,1}x_{1,6}x_{1,2}x_{1,5}x_{3,5}x_{3,4}\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)’s given above for \(p\geq 14\). ◻
Lemma 3.4. There exists a \((6;p,q)\)-decomposition of \(K_3 \Box K_{11}\), \(p\neq 1\).
Proof. First we decompose \(K_3 \Box K_{11}\) into \(C_6\)’s as follows: \[\begin{aligned} &\left\{(x_{1,2}\mathbf{x_{1,1}x_{1,8}x_{1,3}x_{1,9}x_{1,10}x_{1,2}}),\ (\mathbf{x_{1,2}x_{1,4}}x_{1,6}x_{1,1}x_{1,7}x_{1,9}x_{1,2})\right\},\\ &\left\{(x_{1,7}\mathbf{x_{1,11}x_{1,5}x_{1,3}x_{1,10}x_{1,6}x_{1,7}}),\ (x_{1,7}x_{1,10}x_{1,11}x_{1,3}x_{1,2}\mathbf{x_{1,8}x_{1,7}})\right\},\\ &\left\{(x_{1,11}\mathbf{x_{1,8}x_{1,9}x_{1,5}x_{1,10}x_{1,4}x_{1,11}}),\ (x_{1,11}x_{1,9}x_{1,4}x_{1,8}x_{1,5}\mathbf{x_{1,6}x_{1,11}})\right\},\\ &\left\{(x_{2,1}\mathbf{x_{2,11}x_{2,8}x_{2,10}x_{2,4}x_{2,7}x_{2,1}}),\ (\mathbf{x_{2,1}x_{2,2}}x_{2,4}x_{2,5}x_{2,6}x_{2,9}x_{2,1})\right\},\\ &\left\{(x_{2,6}\mathbf{x_{2,3}x_{2,5}x_{2,9}x_{2,7}x_{2,2}x_{2,6}}),\ (\mathbf{x_{2,6}x_{2,10}}x_{2,9}x_{2,2}x_{2,5}x_{2,1}x_{2,6})\right\},\\ &\left\{(x_{2,11}\mathbf{x_{2,6}x_{2,8}x_{2,3}x_{2,10}x_{2,5}x_{2,11}}),\ (\mathbf{x_{2,11}x_{2,2}}x_{2,10}x_{2,7}x_{2,3}x_{2,4}x_{2,11})\right\},\\ &\left\{(x_{3,1}\mathbf{x_{3,11}x_{3,8}x_{3,7}x_{3,9}x_{3,4}x_{3,1}}),\ (\mathbf{x_{3,1}x_{3,3}}x_{3,10}x_{3,11}x_{3,6}x_{3,9}x_{3,1})\right\},\\ &\left\{(x_{3,2}\mathbf{x_{3,3}x_{3,6}x_{3,5}x_{3,9}x_{3,10}x_{3,2}}),\ (\mathbf{x_{3,2}x_{3,8}}x_{3,5}x_{3,10}x_{3,6}x_{3,4}x_{3,2})\right\},\\ &\left\{(x_{3,1}\mathbf{x_{3,2}x_{3,11}x_{3,3}x_{3,8}x_{3,6}x_{3,1}}),\ (x_{3,1}x_{3,8}x_{3,4}x_{3,11}x_{3,7}\mathbf{x_{3,5}x_{3,1}})\right\},\\ &\left\{(x_{1,1}\mathbf{x_{1,3}x_{1,4}x_{2,4}x_{2,1}x_{3,1}x_{1,1}}),\ (\mathbf{x_{1,1}x_{1,5}}x_{3,5}x_{3,3}x_{2,3}x_{2,1}x_{1,1})\right\},\\ &\left\{(x_{2,11}\mathbf{x_{3,11}x_{3,9}x_{1,9}x_{2,9}x_{2,3}x_{2,11}}),\ (\mathbf{x_{2,11}x_{1,11}}x_{1,1}x_{1,10}x_{3,10}x_{2,10}x_{2,11})\right\},\\ &\left\{(x_{1,5}\mathbf{x_{1,7}x_{2,7}x_{3,7}x_{3,4}x_{1,4}x_{1,5}}),\ (\mathbf{x_{1,5}x_{2,5}x_{3,5}}x_{3,11}x_{1,11}x_{1,2}x_{1,5})\right\},\\ &\left\{(x_{1,3}\mathbf{x_{1,6}x_{2,6}x_{2,4}x_{3,4}x_{3,3}x_{1,3}}),\ (\mathbf{x_{1,3}x_{1,7}}x_{3,7}x_{3,2}x_{2,2}x_{2,3}x_{1,3})\right\},\\ &\left\{(x_{2,8}\mathbf{x_{3,8}x_{1,8}x_{1,10}x_{2,10}x_{2,1}x_{2,8}}),\ (\mathbf{x_{2,8}x_{2,4}}x_{2,9}x_{2,11}x_{2,7}x_{2,5}x_{2,8})\right\},\\ &\left\{(x_{3,10}\mathbf{x_{3,4}x_{3,5}x_{3,2}x_{3,6}x_{3,7}x_{3,10}}),\ (\mathbf{x_{3,10}x_{3,8}}x_{3,9}x_{3,3}x_{3,7}x_{3,1}x_{3,10})\right\},\\ &\left\{(x_{2,8}\mathbf{x_{1,8}x_{1,6}x_{3,6}x_{2,6}x_{2,7}x_{2,8}}),\ (\mathbf{x_{2,8}x_{2,9}}x_{3,9}x_{3,2}x_{1,2}x_{2,2}x_{2,8})\right\},\\ &(x_{1,1}x_{1,9}x_{1,6}x_{1,2}x_{1,7}x_{1,4}x_{1,1}). \end{aligned}\]
The last 3\(C_6\) can be decomposed into 3\(P_7\) as follows: \[\{x_{1,1}x_{1,9}x_{1,6}x_{1,8}x_{2,8}x_{2,9}x_{3,9},x_{1,1}x_{1,4}x_{1,7}x_{1,2}x_{1,6}x_{3,6}x_{2,6},x_{2,6}x_{2,7}x_{2,8}x_{2,2}x_{1,2}x_{3,2}x_{3,9}\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)-decomposition given above. ◻
Lemma 3.5. There exists a \((6;p,q)\)-decomposition of \(K_3 \Box K_{16}\), \(p\geq 24\).
Proof. Since the degree of each vertex \(v\in V(K_3 \Box K_{16})\) is odd, \(p\geq \frac{48}{2}=24\). For \(p=24\), the required number of \(C_6\)’s and \(P_7\)’s are constructed as follows: \[\begin{aligned} &\left\{(x_{1,1}\mathbf{x_{1,14}x_{1,3}x_{1,7}x_{1,4}x_{1,8}x_{1,1}}),\ (\mathbf{x_{1,1}x_{1,16}}x_{1,3}x_{1,2}x_{1,8}x_{1,6}x_{1,1})\right\}, \\ &\left\{(x_{1,3}\mathbf{x_{1,9}x_{1,5}x_{1,11}x_{1,2}x_{1,10}x_{1,3}}),\ (\mathbf{x_{1,3}x_{1,12}}x_{1,5}x_{1,10}x_{1,4}x_{1,11}x_{1,3})\right\}, \\ &\left\{(x_{1,9}\mathbf{x_{1,2}x_{1,12}x_{1,1}x_{1,15}x_{1,8}x_{1,9}}),\ (\mathbf{x_{1,9}x_{1,4}}x_{1,16}x_{1,6}x_{1,13}x_{1,7}x_{1,9})\right\}, \\ &\left\{(x_{1,8}\mathbf{x_{1,12}x_{1,7}x_{1,14}x_{1,5}x_{1,13}x_{1,8}}),\ (\mathbf{x_{1,8}x_{1,11}}x_{1,6}x_{1,9}x_{1,1}x_{1,10}x_{1,8})\right\}, \\ &\left\{(x_{1,13}\mathbf{x_{1,3}x_{1,15}x_{1,5}x_{1,16}x_{1,2}x_{1,13}}),\ (\mathbf{x_{1,13}x_{1,4}}x_{1,15}x_{1,7}x_{1,11}x_{1,1}x_{1,13})\right\}, \\ &\left\{(x_{1,14}\mathbf{x_{1,6}x_{1,10}x_{1,7}x_{1,16}x_{1,8}x_{1,14}}),\ (\mathbf{x_{1,14}x_{1,2}}x_{1,15}x_{1,6}x_{1,12}x_{1,4}x_{1,14})\right\}, \\ &\left\{(x_{2,7}\mathbf{x_{2,9}x_{2,3}x_{2,11}x_{2,2}x_{2,10}x_{2,7}}),\ (\mathbf{x_{2,7}x_{2,12}}x_{2,3}x_{2,10}x_{2,5}x_{2,11}x_{2,7})\right\}, \\ &\left\{(x_{2,9}\mathbf{x_{2,2}x_{2,12}x_{2,4}x_{2,15}x_{2,8}x_{2,9}}),\ (\mathbf{x_{2,9}x_{2,5}}x_{2,16}x_{2,6}x_{2,13}x_{2,1}x_{2,9})\right\}, \\ &\left\{(x_{2,8}\mathbf{x_{2,12}x_{2,1}x_{2,14}x_{2,3}x_{2,13}x_{2,8}}),\ (\mathbf{x_{2,8}x_{2,11}}x_{2,6}x_{2,9}x_{2,4}x_{2,10}x_{2,8})\right\}, \\ &\left\{(x_{2,13}\mathbf{x_{2,7}x_{2,15}x_{2,3}x_{2,16}x_{2,2}x_{2,13}}),\ (\mathbf{x_{2,13}x_{2,5}}x_{2,15}x_{2,1}x_{2,11}x_{2,4}x_{2,13})\right\}, \\ &\left\{(x_{2,14}\mathbf{x_{2,6}x_{2,10}x_{2,1}x_{2,16}x_{2,8}x_{2,14}}),\ (\mathbf{x_{2,14}x_{2,2}}x_{2,15}x_{2,6}x_{2,12}x_{2,5}x_{2,14})\right\}, \\ &\left\{(x_{2,4}\mathbf{x_{2,14}x_{2,7}x_{2,6}x_{2,3}x_{2,8}x_{2,4}}),\ (\mathbf{x_{2,4}x_{2,16}}x_{2,7}x_{2,1}x_{2,8}x_{2,5}x_{2,4})\right\}, \\ &\left\{(x_{3,1}\mathbf{x_{3,9}x_{3,3}x_{3,11}x_{3,5}x_{3,10}x_{3,1}}),\ (\mathbf{x_{3,1}x_{3,12}}x_{3,3}x_{3,10}x_{3,4}x_{3,11}x_{3,1})\right\}, \\ &\left\{(x_{3,9}\mathbf{x_{3,5}x_{3,12}x_{3,2}x_{3,15}x_{3,8}x_{3,9}}),\ (\mathbf{x_{3,9}x_{3,4}}x_{3,16}x_{3,6}x_{3,13}x_{3,7}x_{3,9})\right\}, \\ &\left\{(x_{3,8}\mathbf{x_{3,12}x_{3,7}x_{3,14}x_{3,3}x_{3,13}x_{3,8}}),\ (\mathbf{x_{3,8}x_{3,11}}x_{3,6}x_{3,9}x_{3,2}x_{3,10}x_{3,8})\right\}, \\ &\left\{(x_{3,13}\mathbf{x_{3,1}x_{3,15}x_{3,3}x_{3,16}x_{3,5}x_{3,13}}),\ (\mathbf{x_{3,13}x_{3,4}}x_{3,15}x_{3,7}x_{3,11}x_{3,2}x_{3,13}\right\}, \\ &\left\{(x_{3,14}\mathbf{x_{3,6}x_{3,10}x_{3,7}x_{3,16}x_{3,8}x_{3,14}}),\ (\mathbf{x_{3,14}x_{3,5}}x_{3,15}x_{3,6}x_{3,12}x_{3,4}x_{3,14}\right\}, \\ &\left\{(x_{3,2}\mathbf{x_{3,14}x_{3,1}x_{3,5}x_{3,8}x_{3,3}x_{3,2}}),\ (\mathbf{x_{3,2}x_{3,16}}x_{3,1}x_{3,7}x_{3,6}x_{3,8}x_{3,2})\right\}, \\ &\left\{(x_{1,10}\mathbf{x_{1,11}x_{1,15}x_{1,12}x_{1,14}x_{1,16}x_{1,10}}),\ (\mathbf{x_{1,10}x_{1,13}}x_{1,12}x_{1,16}x_{1,9}x_{1,14}x_{1,10})\right\}, \\ &\left\{(x_{2,14}\mathbf{x_{1,14}x_{3,14}x_{3,10}x_{3,13}x_{2,13}x_{2,14}}),\ (\mathbf{x_{2,14}x_{2,10}}x_{2,13}x_{2,12}x_{2,16}x_{2,9}x_{2,14})\right\}, \\ &\left\{(x_{3,11}\mathbf{x_{3,14}x_{3,15}x_{3,9}x_{3,13}x_{3,16}x_{3,11}}),\ (x_{3,11}x_{3,15}x_{3,12}x_{3,14}x_{3,16}\mathbf{x_{3,10}x_{3,11}})\right\}, \\ &\left\{(x_{1,4}x_{1,5}x_{2,5}x_{2,2}x_{2,6}x_{1,6}x_{1,4}),\ (x_{3,2}x_{3,5}x_{3,7}x_{3,8}x_{3,4}x_{3,6}x_{3,2})\right\}, \end{aligned}\] \[\begin{aligned} &x_{1,2}x_{1,6}x_{3,6}x_{3,3}x_{3,7}x_{3,4}x_{2,4},x_{1,1}x_{1,2}x_{1,5}x_{1,8}x_{1,3}x_{3,3}x_{2,3}, x_{2,5}x_{2,1}x_{2,2}x_{2,7}x_{2,8}x_{2,6}x_{3,6},x_{2,6}x_{2,1}x_{2,4}x_{1,4}x_{1,1}x_{1,5}x_{3,5}, \\ &x_{2,1}x_{1,1}x_{3,1}x_{3,3}x_{3,4}x_{3,2}x_{3,7},x_{1,4}x_{1,3}x_{1,6}x_{1,5}x_{1,7}x_{3,7}x_{2,7}, x_{1,5}x_{1,3}x_{1,1}x_{1,7}x_{1,8}x_{3,8}x_{2,8},x_{2,2}x_{1,2}x_{3,2}x_{3,1}x_{3,6}x_{3,5}x_{3,3}, \\ &x_{3,1}x_{2,1}x_{2,3}x_{2,7}x_{2,4}x_{2,2}x_{3,2},x_{1,7}x_{2,7}x_{2,5}x_{2,3}x_{2,2}x_{2,8}x_{1,8}, x_{1,6}x_{1,7}x_{1,2}x_{1,4}x_{3,4}x_{3,1}x_{3,8},x_{1,3}x_{2,3}x_{2,4}x_{2,6}x_{2,5}x_{3,5}x_{3,4}, \\ &\quad\quad x_{1,9}x_{1,12}x_{2,12}x_{3,12}x_{3,16}x_{3,15}x_{3,13},x_{1,10}x_{1,9}x_{1,13}x_{1,16}x_{1,11}x_{3,11}x_{2,11}, x_{1,11}x_{2,11}x_{2,12}x_{2,14}x_{2,15}x_{2,9}x_{2,13},\\&\quad\quad x_{1,12}x_{1,11}x_{1,14}x_{1,13}x_{1,15}x_{3,15}x_{2,15}, x_{1,13}x_{1,11}x_{1,9}x_{1,15}x_{1,16}x_{3,16}x_{2,16}, x_{1,14}x_{1,15}x_{1,10}x_{1,12}x_{3,12}x_{3,9}x_{3,16}, \\ &\quad\quad x_{1,15}x_{2,15}x_{2,13}x_{2,11}x_{2,10}x_{2,16}x_{1,16}, x_{2,9}x_{1,9}x_{3,9}x_{3,11}x_{3,12}x_{3,10}x_{3,15}, x_{2,10}x_{1,10}x_{3,10}x_{3,9}x_{3,14}x_{3,13}x_{3,11},\\&\quad\quad x_{2,12}x_{2,9}x_{2,10}x_{2,15}x_{2,16}x_{2,14}x_{3,14}, x_{2,14}x_{2,11}x_{2,16}x_{2,13}x_{1,13}x_{3,13}x_{3,12}, x_{3,9}x_{2,9}x_{2,11}x_{2,15}x_{2,12}x_{2,10}x_{3,10}. \end{aligned}\]
For \(p =\) \(25\), we decompose the last cycle and first path into 2\(P_7\) as follows: \[x_{1,2}x_{1,6}x_{3,6}x_{3,3}x_{3,7}x_{3,4}x_{3,8},x_{2,4}x_{3,4}x_{3,6}x_{3,2}x_{3,5}x_{3,7}x_{3,8}.\]
For \(p=26\), we can decompose \[\{(x_{1,4}x_{1,5}x_{2,5}x_{2,2}x_{2,6}x_{1,6}x_{1,4}),x_{1,1}x_{1,2}x_{1,5}x_{1,8}x_{1,3}x_{3,3}x_{2,3}\},\] into 2\(P_7\) in \(p=25\) as follows: \[x_{1,1}x_{1,2}x_{1,5}x_{2,5}x_{2,2}x_{2,6}x_{1,6},x_{1,6}x_{1,4}x_{1,5}x_{1,8}x_{1,3}x_{3,3}x_{2,3}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from paired \(C_6\)’s given above for \(p\geq 27\). So, we have the desired decomposition for \(K_3 \Box K_{16}\). ◻
Lemma 3.6. There exists a \((6;p,q)\)-decomposition of \(K_6 \Box K_2\), \(p\neq 1\).
Proof. First we decompose \(K_6 \Box K_2\) into \(C_6\)’s as follows:
\(\left\{(x_{1,2}\mathbf{x_{5,2}x_{4,2}x_{3,2}x_{2,2}x_{6,2}x_{1,2}}),\
(\mathbf{x_{2,1}x_{4,1}}x_{4,2}x_{6,2}x_{6,1}x_{5,1}x_{2,1})\right\}\),
\(\left\{(x_{3,2}\mathbf{x_{6,2}x_{5,2}x_{2,2}x_{4,2}x_{1,2}x_{3,2}}),\
(\mathbf{x_{3,2}x_{3,1}}x_{6,1}x_{1,1}x_{5,1}x_{5,2}x_{3,2})\right\}\),
\(\left\{(x_{1,1}\mathbf{x_{2,1}x_{6,1}x_{4,1}x_{5,1}x_{3,1}x_{1,1}}),\
(\mathbf{x_{1,1}x_{1,2}}x_{2,2}x_{2,1}x_{3,1}x_{4,1}x_{1,1})\right\}\).
The last 3\(C_6\) can be decomposed into 3\(P_7\) as follows: \[\{x_{2,1}x_{3,1}x_{5,1}x_{4,1}x_{1,1}x_{1,2}x_{2,2}, x_{2,2}x_{2,1}x_{1,1}x_{6,1}x_{3,1}x_{3,2}x_{5,2}, x_{2,1}x_{6,1}x_{4,1}x_{3,1}x_{1,1}x_{5,1}x_{5,2}\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)-decomposition given above. ◻
Lemma 3.7. There exists a \((6;p,q)\)-decomposition of \(K_6 \Box K_4\), \(p\neq 1\).
Proof. First we decompose \(K_6 \Box K_4\) into \(C_6\)’s as follows:
\(\left\{(x_{3,3}\mathbf{x_{1,3}x_{2,3}x_{2,4}x_{3,4}x_{3,2}x_{3,3}}),\
(\mathbf{x_{3,3}x_{4,3}}x_{4,4}x_{6,4}x_{6,3}x_{5,3}x_{3,3})\right\}\),
\(\left\{(x_{1,3}\mathbf{x_{1,1}x_{1,2}x_{2,2}x_{2,4}x_{1,4}x_{1,3}}),\
(\mathbf{x_{1,3}x_{6,3}}x_{3,3}x_{3,4}x_{5,4}x_{5,3}x_{1,3})\right\}\),
\(\left\{(x_{4,2}\mathbf{x_{3,2}x_{5,2}x_{6,2}x_{6,3}x_{4,3}x_{4,2}}),\
(\mathbf{x_{4,2}x_{4,1}}x_{3,1}x_{6,1}x_{6,4}x_{6,2}x_{4,2})\right\}\),
\(\left\{(x_{1,2}\mathbf{x_{3,2}x_{2,2}x_{2,1}x_{1,1}x_{1,4}x_{1,2}}),\
(\mathbf{x_{1,2}x_{1,3}}x_{4,3}x_{2,3}x_{2,2}x_{4,2}x_{1,2})\right\}\),
\(\left\{(x_{6,1}\mathbf{x_{6,3}x_{2,3}x_{5,3}x_{4,3}x_{4,1}x_{6,1}}),\
(\mathbf{x_{6,1}x_{1,1}}x_{5,1}x_{5,4}x_{2,4}x_{2,1}x_{6,1})\right\}\),
\(\left\{(x_{3,1}\mathbf{x_{1,1}x_{4,1}x_{2,1}x_{2,3}x_{3,3}x_{3,1}}),\
(\mathbf{x_{3,1}x_{5,1}}x_{5,2}x_{1,2}x_{6,2}x_{3,2}x_{3,1})\right\}\),
\(\left\{(x_{1,4}\mathbf{x_{6,4}x_{5,4}x_{5,2}x_{4,2}x_{4,4}x_{1,4}}),\
(x_{1,4}x_{5,4}x_{4,4}x_{2,4}x_{6,4}\mathbf{x_{3,4}x_{1,4}})\right\}\),
\(\left\{(x_{5,1}\mathbf{x_{2,1}x_{3,1}x_{3,4}x_{4,4}x_{4,1}x_{5,1}}),\
(\mathbf{x_{5,1}x_{6,1}}x_{6,2}x_{2,2}x_{5,2}x_{5,3}x_{5,1})\right\}\).
The first 3\(C_6\) can be decomposed into 3\(P_7\) as follows: \[\{x_{1,1}x_{1,2}x_{2,2}x_{2,4}x_{1,4}x_{1,3}x_{2,3}, x_{2,3}x_{2,4}x_{3,4}x_{3,2}x_{3,3}x_{4,3}x_{4,4}, x_{6,4}x_{6,3}x_{5,3}x_{3,3}x_{1,3}x_{1,1}\}.\]
Now, using Construction 1.4 we get the required number of paths
and cycles from the
\(C_6\)-decomposition given
above. ◻
Lemma 3.8. There exists a \((6;p,q)\)-decomposition of \(K_6 \Box K_6\), \(p\neq 1\).
Proof. First we decompose \(K_6 \Box K_6\) into \(C_6\)’s as follows:
\(\left\{(x_{1,1}\mathbf{x_{1,2}x_{2,2}x_{3,2}x_{6,2}x_{6,1}x_{1,1}}),\
(\mathbf{x_{1,1}x_{3,1}}x_{4,1}x_{5,1}x_{6,1}x_{2,1}x_{1,1})\right\}\),
\(\left\{(\mathbf{x_{2,1}x_{2,2}}x_{4,2}x_{4,3}x_{4,4}x_{4,1}x_{2,1}),\
(x_{2,1}\mathbf{x_{3,1}x_{6,1}x_{4,1}x_{1,1}x_{5,1}x_{2,1}})\right\}\),
\(\left\{(x_{1,2}\mathbf{x_{1,4}x_{1,1}x_{1,3}x_{3,3}x_{3,2}x_{1,2}}),\
(x_{1,2}x_{1,3}x_{4,3}x_{4,1}x_{4,2}\mathbf{x_{6,2}x_{1,2}})\right\}\)
\(\left\{(x_{1,3}\mathbf{x_{5,3}x_{5,1}x_{5,2}x_{6,2}x_{6,3}x_{1,3}}),\
(\mathbf{x_{1,3}x_{1,6}}x_{1,4}x_{6,4}x_{6,5}x_{1,5}x_{1,3})\right\}\),
\(\left\{(x_{1,4}\mathbf{x_{1,5}x_{3,5}x_{2,5}x_{5,5}x_{5,4}x_{1,4}}),\
(\mathbf{x_{1,4}x_{4,4}}x_{5,4}x_{2,4}x_{6,4}x_{3,4}x_{1,4})\right\}\),
\(\left\{(x_{1,5}\mathbf{x_{5,5}x_{5,1}x_{5,6}x_{5,2}x_{1,2}x_{1,5}}),\
(\mathbf{x_{1,5}x_{4,5}}x_{4,2}x_{1,2}x_{1,6}x_{1,1}x_{1,5})\right\}\)
\(\left\{(x_{1,6}\mathbf{x_{6,6}x_{3,6}x_{4,6}x_{2,6}x_{5,6}x_{1,6}}),\
(x_{1,6}x_{4,6}x_{6,6}x_{2,6}x_{2,5}\mathbf{x_{1,5}x_{1,6}})\right\}\),
\(\left\{(x_{3,3}\mathbf{x_{2,3}x_{6,3}x_{5,3}x_{5,4}x_{3,4}x_{3,3}}),\
(\mathbf{x_{3,3}x_{4,3}}x_{4,5}x_{6,5}x_{5,5}x_{5,3}x_{3,3})\right\}\),
\(\left\{(x_{5,6}\mathbf{x_{4,6}x_{4,4}x_{2,4}x_{2,6}x_{3,6}x_{5,6}}),\
(\mathbf{x_{5,6}x_{6,6}}x_{6,4}x_{4,4}x_{4,5}x_{5,5}x_{5,6})\right\}\)
\(\left\{(x_{3,4}\mathbf{x_{3,5}x_{4,5}x_{4,6}x_{4,2}x_{4,4}x_{3,4}}),\
(\mathbf{x_{3,4}x_{2,4}}x_{2,3}x_{2,6}x_{1,6}x_{3,6}x_{3,4})\right\}\),
\(\left\{(x_{6,3}\mathbf{x_{6,4}x_{5,4}x_{5,6}x_{5,3}x_{4,3}x_{6,3}}),\
(\mathbf{x_{6,3}x_{3,3}}x_{3,5}x_{6,5}x_{6,1}x_{6,6}x_{6,3})\right\}\),
\(\left\{(x_{2,3}\mathbf{x_{2,5}x_{4,5}x_{4,1}x_{4,6}x_{4,3}x_{2,3}}),\
(\mathbf{x_{2,3}x_{2,2}}x_{2,5}x_{2,4}x_{1,4}x_{1,3}x_{2,3})\right\}\),
\(\left\{(x_{3,1}\mathbf{x_{3,6}x_{3,2}x_{5,2}x_{5,5}x_{3,5}x_{3,1}}),\
(\mathbf{x_{3,1}x_{3,4}}x_{3,2}x_{3,5}x_{3,6}x_{3,3}x_{3,1})\right\}\),
\(\left\{(x_{6,2}\mathbf{x_{6,4}x_{6,1}x_{6,3}x_{6,5}x_{6,6}x_{6,2}}),\
(x_{6,2}x_{6,5}x_{2,5}x_{2,1}x_{2,6}\mathbf{x_{2,2}x_{6,2}})\right\}\),
\(\left\{(x_{5,2}\mathbf{x_{5,4}x_{5,1}x_{3,1}x_{3,2}x_{4,2}x_{5,2}}),\
(\mathbf{x_{5,2}x_{5,3}}x_{2,3}x_{2,1}x_{2,4}x_{2,2}x_{5,2})\right\}\).
The first 3\(C_6\) can be decomposed into 3\(P_7\) as follows: \[\{x_{4,4}x_{4,3}x_{4,2}x_{2,2}x_{3,2}x_{6,2}x_{6,1}, x_{4,4}x_{4,1}x_{5,1}x_{6,1}x_{1,1}x_{2,1}x_{2,2}, x_{6,1}x_{2,1}x_{4,1}x_{3,1}x_{1,1}x_{1,2}x_{2,2}\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)-decomposition given above. ◻
Lemma 3.9. There exists a \((6;p,q)\)-decomposition of \(K_6 \Box K_{8}\), \(p\neq 1\).
Proof. By Lemma 2.2, \(K_8-I\) has a \((6;p,q)\)-decomposition. We decompose \(8K_6\ \oplus\ 6I\) into \(C_6\)’s as follows: \[\begin{aligned} &\left\{(x_{3,j}x_{2,j}x_{6,j}\mathbf{x_{4,j}x_{5,j}x_{1,j}x_{3,j}}),\ (\mathbf{x_{3,j}x_{5,j}x_{5,j+1}}x_{1,j+1}x_{1,j}x_{6,j}x_{3,j})\right\}, \\ &\left\{(x_{3,j+1}x_{2,j+1}\mathbf{x_{2,j}x_{1,j}x_{4,j}x_{3,j}x_{3,j+1}}),\right. \left. (\mathbf{x_{3,j+1}x_{4,j+1}}x_{5,j+1}x_{6,j+1}x_{2,j+1}x_{1,j+1}x_{3,j+1})\right\},\\ &\left\{(x_{4,j+1}\mathbf{x_{1,j+1}x_{6,j+1}x_{3,j+1}x_{5,j+1}x_{2,j+1}x_{4,j+1}}),\right., \left. (\mathbf{x_{4,j+1}x_{4,j}}x_{2,j}x_{5,j}x_{6,j}x_{6,j+1}x_{4,j+1}) \right\}, \end{aligned}\] where \(j=1,3,\cdots ,7\). The first 3\(C_6\) can be decomposed into 3\(P_7\) as follows: \[\{x_{3,j+1}x_{2,j+1}x_{2,j}x_{3,j}x_{6,j}x_{1,j}x_{1,j+1}, x_{6,j}x_{4,j}x_{1,j}x_{3,j}x_{5,j}x_{5,j+1}x_{1,j+1}, x_{6,j}x_{2,j}x_{1,j}x_{5,j}x_{4,j}x_{3,j}x_{3,j+1}\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)-decomposition given above. ◻
Lemma 3.10. There exists a \((6;p,q)\)-decomposition of \(K_4 \Box K_4\), \(p\neq 1\).
Proof. First we decompose \(K_4 \Box K_4\) into \(C_6\)’s as follows:
\(\left\{(x_{2,1}\mathbf{x_{4,1}x_{1,1}x_{1,2}x_{2,2}x_{2,3}x_{2,1}}),\
(\mathbf{x_{2,1}x_{3,1}}x_{3,4}x_{3,2}x_{2,2}x_{2,4}x_{2,1})\right\}\),
\(\left\{(x_{2,3}\mathbf{x_{1,3}x_{1,4}x_{3,4}x_{4,4}x_{2,4}x_{2,3}}),\
(\mathbf{x_{2,3}x_{3,3}}x_{3,1}x_{3,2}x_{4,2}x_{4,3}x_{2,3})\right\}\),
\(\left\{(x_{1,1}\mathbf{x_{1,3}x_{3,3}x_{3,2}x_{1,2}x_{1,4}x_{1,1}}),\
(x_{1,1}x_{1,2}x_{2,2}x_{4,2}x_{4,1}\mathbf{x_{3,1}x_{1,1}})\right\}\),
\(\left\{(x_{4,4}\mathbf{x_{1,4}x_{2,4}x_{3,4}x_{3,3}x_{4,3}x_{4,4}}),\
(\mathbf{x_{4,4}x_{4,2}}x_{1,2}x_{1,3}x_{4,3}x_{4,1}x_{4,4})\right\}\).
The first \(3C_6\) can be decomposed into 3\(P_7\) as follows: \[\{x_{1,1}x_{1,2}x_{2,2}x_{2,4}x_{2,1}x_{2,3}x_{1,3}, x_{1,3}x_{1,4}x_{3,4}x_{3,2}x_{2,2}x_{2,3}x_{2,4}, x_{1,1}x_{4,1}x_{2,1}x_{3,1}x_{3,4}x_{4,4}x_{2,4}\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)-decomposition given above. ◻
Lemma 3.11. There exists a \((6;p,q)\)-decomposition of \(K_7 \Box K_{7}\), \(p\neq 1\).
Proof. We can write \(K_7 \Box K_{7}=7K_7\backslash E(K_3)\ \oplus\ K_3\ \oplus\ 7K_7\backslash E(K_3)\ \oplus\ K_3\). By Lemma 2.1, \(K_7\backslash E(K_3)\) has a \((6;p,q)\)-decomposition. Now, we can view \(7K_3\ \oplus\ 7K_3\) as \(K_3^1\ \oplus\ \cdots\ \oplus\ K_3^7\ \oplus\ (K_3^1)'\ \oplus\ \cdots\ \oplus\ (K_3^7)'\) with \(K_3^i=(x_{i,i-2}x_{i,i-1}x_{i,i}x_{i,i-2})\), for \(i=1,\cdots ,7\) and \((K_3^i)'=(x_{i,i}x_{i+1,i}x_{i+2,i}x_{i,i})\), for \(i=1,\cdots ,7\), where the subscripts of \(x\) are taken modulo 7 with residues \(\{1,\cdots,7\}\). The \(C_6\)-decomposition of \(7K_3\ \oplus\ 7K_3\) is given below: \[\begin{aligned} &\left\{(x_{3,1}\mathbf{x_{1,1}x_{2,1}x_{2,7}x_{2,2}x_{3,2}x_{3,1}}),\ (\mathbf{x_{3,1}x_{3,3}}x_{3,2}x_{4,2}x_{2,2}x_{2,1}x_{3,1})\right\},\\ &\left\{(x_{4,4}\mathbf{x_{4,2}x_{4,3}x_{3,3}x_{5,3}x_{5,4}x_{4,4}}),\ (\mathbf{x_{4,4}x_{6,4}}x_{5,4}x_{5,5}x_{5,3}x_{4,3}x_{4,4})\right\},\\ &\left\{(\mathbf{x_{7,7}x_{1,7}x_{1,6}x_{6,6}x_{6,5}x_{7,5}}x_{7,7}),\ (\mathbf{x_{7,7}x_{2,7}}x_{1,7}x_{1,1}x_{1,6}x_{7,6}x_{7,7})\right\},\\ &(x_{5,5}x_{6,5}x_{6,4}x_{6,6}x_{7,6}x_{7,5}x_{5,5}).\end{aligned}\]
The last 3\(C_6\) can be decomposed into 3\(P_7\) as follows: \[\{x_{1,1}x_{1,7}x_{2,7}x_{7,7}x_{7,6}x_{7,5}x_{5,5}, x_{5,5}x_{6,5}x_{6,4}x_{6,6}x_{7,6}x_{1,6}x_{1,7}, x_{1,1}x_{1,6}x_{6,6}x_{6,5}x_{7,5}x_{7,7}x_{1,7}\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)-decomposition given above. ◻
Lemma 3.12. There exists a \((6;p,q)\)-decomposition of \(K_3 \Box K_{12}\), \(p\geq 18\).
Proof. Since the degree of each vertex \(v\in V(K_3 \Box K_{12})\) is odd, then \(p\geq \frac{36}{2}=18\). We can write \(K_3 \Box K_{12} = 12K_3\ \oplus\ 3K_{12} = 12K_3\ \oplus\ 3((K_{12}\backslash E(2C_6))\) \(\oplus\ 2C_6)\). The graph \(12K_3\) along with three rows of \(2C_6\) can be viewed as \(2G\), where \(G=6K_3\ \oplus\ C_6^1\ \oplus\ C_6^2\ \oplus\ C_6^3\) with \(V(G)=\left\{x_{i,j}:1\leq i\leq 3, 1\leq j\leq 6\right\}\) and \(C_6^1=(x_{1,1}x_{1,2}x_{1,5}x_{1,4}x_{1,6}x_{1,3}x_{1,1}\), \(C_6^2=(x_{2,1}x_{2,2}x_{2,4}x_{2,5}x_{2,3}x_{2,6}x_{2,1})\), \(C_6^3=(x_{3,1}x_{3,2}x_{3,6}x_{3,4}x_{3,3}x_{3,5}x_{3,1})\) and decompose \(G\) into \(C_6\)’s as follows:
\(\left\{(x_{1,1}\mathbf{x_{1,2}x_{1,5}x_{2,5}x_{2,3}x_{1,3}x_{1,1}}),\
(\mathbf{x_{1,1}x_{2,1}}x_{2,2}x_{1,2}x_{3,2}x_{3,1}x_{1,1})\right\}\),
\(\left\{(x_{1,6}\mathbf{x_{1,4}x_{2,4}x_{2,2}x_{3,2}x_{3,6}x_{1,6}}),\
(\mathbf{x_{1,6}x_{2,6}}x_{3,6}x_{3,4}x_{3,3}x_{1,3}x_{1,6})\right\}\),
\(\left\{(x_{3,5}\mathbf{x_{2,5}x_{2,4}x_{3,4}x_{1,4}x_{1,5}x_{3,5}}),\
(\mathbf{x_{3,5}x_{3,1}}x_{2,1}x_{2,6}x_{2,3}x_{3,3}x_{3,5})\right\}\).
The first 3\(C_6\) can be decomposed into 3\(P_7\) as follows: \[\{x_{2,1}x_{2,2}x_{1,2}x_{1,1}x_{3,1}x_{3,2}x_{3,6}, x_{2,1}x_{1,1}x_{1,3}x_{2,3}x_{2,5}x_{1,5}x_{1,2}, x_{1,2}x_{3,2}x_{2,2}x_{2,3}x_{1,3}x_{1,6}x_{3,6}\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)-decomposition given above. So, \(G\) has a \((6;p,q)\)-decomposition. By Lemma 2.5, the remaining edges has a \((6;p,q)\)-decomposition. ◻
Lemma 3.13. There exists a \((6;p,q)\)-decomposition of \(K_5 \Box K_{12}\), \(p\geq 30\).
Proof. Since the degree of each vertex \(v\in V(K_5 \Box K_{12})\) is odd, then \(p\geq 30\). We can write \(K_5 \Box K_{12}\) \(=12K_5\ \oplus\ 5K_{12}=12K_5\ \oplus\ 5((K_{12}\backslash E(2C_6))\ \oplus\ 2C_6)\). By Lemma 2.5, \(K_{12}\backslash E(2C_6)\) has a \((6;p,q)\)-decomposition. Let \(12K_5\ \oplus\ 10C_6=G_1\ \oplus\ G_2\), where \(G_1 = (6K_5\ \oplus\ C_6^1\ \oplus\ \cdots\ \oplus\ C_6^5)\cong G_2\) with
\[\begin{aligned}&C_6^1=(x_{1,1}x_{1,2}x_{1,4}x_{1,6}x_{1,5}x_{1,3}x_{1,1}), C_6^2=(x_{2,1}x_{2,5}x_{2,3}x_{2,6}x_{2,2}x_{2,4}x_{2,1}), \\ &C_6^3=(x_{3,1}x_{3,3}x_{3,5}x_{3,2}x_{3,6}x_{3,4}x_{3,1}), C_6^4=(x_{4,1}x_{4,5}x_{4,2}x_{4,4}x_{4,6}x_{4,3}x_{4,1}),\\ &C_6^5=(x_{5,1}x_{5,2}x_{5,4}x_{5,6}x_{5,5}x_{5,3}x_{5,1}).\end{aligned}\]
The graph \(G_1\) decomposes into required number of \(C_6\) as follows: \[\begin{aligned} &\left\{(x_{1,2}\mathbf{x_{1,4}x_{5,4}x_{4,4}x_{4,2}x_{3,2}x_{1,2}}),\ (\mathbf{x_{1,2}x_{2,2}}x_{2,4}x_{3,4}x_{5,4}x_{5,2}x_{1,2})\right\},\\ &\left\{(x_{1,6}\mathbf{x_{2,6}x_{3,6}x_{3,4}x_{4,4}x_{1,4}x_{1,6}}),\ (x_{1,6}x_{3,6}x_{5,6}x_{5,5}x_{2,5}\mathbf{x_{1,5}x_{1,6}})\right\},\\ &\left\{(x_{1,3}\mathbf{x_{2,3}x_{2,6}x_{5,6}x_{4,6}x_{4,3}x_{1,3}}),\ (\mathbf{x_{1,3}x_{1,5}}x_{5,5}x_{3,5}x_{3,3}x_{5,3}x_{1,3})\right\},\\ &\left\{(x_{2,1}\mathbf{x_{2,5}x_{3,5}x_{4,5}x_{4,1}x_{1,1}x_{2,1}}),\ (\mathbf{x_{2,1}x_{2,4}}x_{1,4}x_{3,4}x_{3,1}x_{4,1}x_{2,1})\right\},\\ &\left\{(x_{4,2}\mathbf{x_{5,2}x_{5,1}x_{3,1}x_{1,1}x_{1,2}x_{4,2}}),\ (\mathbf{x_{4,2}x_{2,2}}x_{3,2}x_{3,5}x_{1,5}x_{4,5}x_{4,2})\right\},\\ &\left\{(x_{4,6}\mathbf{x_{3,6}x_{3,2}x_{5,2}x_{2,2}x_{2,6}x_{4,6}}),\ (\mathbf{x_{4,6}x_{1,6}}x_{5,6}x_{5,4}x_{2,4}x_{4,4}x_{4,6})\right\},\\ &\left\{(x_{3,3}\mathbf{x_{4,3}x_{4,1}x_{5,1}x_{1,1}x_{1,3}x_{3,3}}),\ (\mathbf{x_{3,3}x_{2,3}}x_{5,3}x_{5,1}x_{2,1}x_{3,1}x_{3,3})\right\},\\ &(x_{2,3}x_{2,5}x_{4,5}x_{5,5}x_{5,3}x_{4,3}x_{2,3}). \end{aligned}\]
The last 3\(C_6\) can be decomposed into 3\(P_7\) as follows: \[\{x_{5,5}x_{5,3}x_{2,3}x_{4,3}x_{4,1}x_{5,1}x_{2,1}, x_{2,1}x_{3,1}x_{3,3}x_{1,3}x_{1,1}x_{5,1}x_{5,3}, x_{5,3}x_{4,3}x_{3,3}x_{2,3}x_{2,5}x_{4,5}x_{5,5}\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)-decomposition given above. Hence \(G_1\) has a \((6;p,q)\)-decomposition and so the graph \(G_2\). ◻
Lemma 3.14. There exists a \((6;p,q)\)-decomposition of \(K_7 \Box K_{12}\), \(p\geq 42\).
Proof. Since the degree of each vertex \(v\in V(K_7 \Box K_{12})\) is odd, then \(p\geq 42\). We can write \(K_7 \Box K_{12}=12K_7\ \oplus\ 7K_{12}=12(K_7\backslash E(K_3))\ \oplus\ 4K_{12}\ \oplus\ (K_3 \Box K_{12})\). By Lemmas 2.1, 2.8 and 3.12, the given graph has a \((6;p,q)\)-decomposition. ◻
Lemma 3.15. There exists a \((6;p,q)\)-decomposition of \(K_{11} \Box K_{12}\), \(p\geq 66\).
Proof. Since the degree of each vertex \(v\in V(K_{11} \Box K_{12})\) is odd, then \(p\geq 66\). We can write \(K_{11} \Box K_{12} = 12K_{11}\ \oplus\ 11K_{12} = 12(K_{11}\backslash E(C_7))\ \oplus\ 11K_{12}\). Consider \(K_{12}\) in rows 1, 3, 4, 7 as \((K_{12}\backslash E(2C_6))\ \oplus\ 2C_6\), where 2\(C_6\) are vertex disjoint cycles. Now, these 8\(C_6\) along with 12\(C_7\) in columns form a graph \(G = (4C_6\oplus 6C_7)\ \oplus\ (4C_6\oplus 6C_7) = G_1\ \oplus\ G_2\), \(G_1\cong G_2\). Let \(G_1=C_6^1\ \oplus\ \cdots\ \oplus\ C_6^4\ \oplus\ C_7^1\ \oplus\ \cdots\ \oplus\ C_7^6\), where \[\begin{aligned} &C_6^1=(x_{1,1}x_{1,2}x_{1,5}x_{1,6}x_{1,4}x_{1,3}x_{1,1}), C_6^2=(x_{3,1}x_{3,2}x_{3,3}x_{3,6}x_{3,4}x_{3,5}x_{3,1}),\\ &C_6^3=(x_{4,1}x_{4,2}x_{4,5}x_{4,6}x_{4,4}x_{4,3}x_{4,1}), C_6^4=(x_{7,1}x_{7,2}x_{7,3}x_{7,4}x_{7,5}x_{7,6}x_{7,1}), \end{aligned}\] and \[\begin{aligned} &C_7^1=(x_{1,1}x_{2,1}x_{4,1}x_{7,1}x_{3,1}x_{5,1}x_{6,1}x_{1,1}), C_7^2=(x_{1,2}x_{3,2}x_{7,2}x_{6,2}x_{5,2}x_{4,2}x_{2,2}x_{1,2}),\\ &C_7^3=(x_{1,3}x_{3,3}x_{5,3}x_{6,3}x_{7,3}x_{4,3}x_{2,3}x_{1,3}), C_7^4=(x_{1,4}x_{2,4}x_{3,4}x_{7,4}x_{6,4}x_{5,4}x_{4,4}x_{1,4}),\\ &C_7^5=(x_{1,5}x_{3,5}x_{5,5}x_{6,5}x_{7,5}x_{4,5}x_{2,5}x_{1,5}), C_7^6=(x_{1,6}x_{2,6}x_{3,6}x_{4,6}x_{5,6}x_{6,6}x_{7,6}x_{1,6}). \end{aligned}\]
This can be decomposed into required number of \(C_6\) as follows: \[\begin{aligned} &\left\{(x_{1,2}\mathbf{x_{3,2}x_{3,1}x_{5,1}x_{6,1}x_{1,1}x_{1,2}}),\ (\mathbf{x_{1,2}x_{1,5}}x_{2,5}x_{4,5}x_{4,2}x_{2,2}x_{1,2})\right\},\\ &\left\{(x_{7,2}\mathbf{x_{7,1}x_{4,1}x_{4,2}x_{5,2}x_{6,2}x_{7,2}}),\ (\mathbf{x_{7,2}x_{3,2}}x_{3,3}x_{5,3}x_{6,3}x_{7,3}x_{7,2})\right\},\\ &\left\{(x_{7,4}\mathbf{x_{7,3}x_{4,3}x_{4,4}x_{5,4}x_{6,4}x_{7,4}}),\ (\mathbf{x_{7,4}x_{3,4}}x_{3,5}x_{5,5}x_{6,5}x_{7,5}x_{7,4})\right\},\\ &\left\{(x_{7,6}\mathbf{x_{7,5}x_{4,5}x_{4,6}x_{5,6}x_{6,6}x_{7,6}}),\ (\mathbf{x_{7,6}x_{7,1}}x_{3,1}x_{3,5}x_{1,5}x_{1,6}x_{7,6})\right\},\\ &\left\{(x_{1,3}\mathbf{x_{1,4}x_{2,4}x_{3,4}x_{3,6}x_{3,3}x_{1,3}}),\ (\mathbf{x_{1,3}x_{2,3}}x_{4,3}x_{4,1}x_{2,1}x_{1,1}x_{1,3})\right\},\\ &(x_{1,4}x_{1,6}x_{2,6}x_{3,6}x_{4,6}x_{4,4}x_{1,4}). \end{aligned}\]
The last 3\(C_6\) can be decomposed into 3\(P_7\) as follows: \[\{x_{4,1}x_{2,1}x_{1,1}x_{1,3}x_{1,4}x_{1,6}x_{2,6}, x_{2,6}x_{3,6}x_{4,6}x_{4,4}x_{1,4}x_{2,4}x_{3,4}, x_{3,4}x_{3,6}x_{3,3}x_{1,3}x_{2,3}x_{4,3}x_{4,1}\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)-decomposition given above. Hence \(G_1\) also has a \((6;p,q)\)-decomposition and so the graph \(G_2\). Also by Lemmas 2.5, 2.7, \(K_{11}\backslash E(C_7)\) and \(K_{12}\backslash E(C_6)\) have a \((6;p,q)\)-decomposition. Hence by Remark 1.3, \(K_{11} \Box K_{12}\) has a \((6;p,q)\)-decomposition. ◻
Lemma 3.16. There exists a \((6;p,q)\)-decomposition of \(C_6 \Box (K_8\backslash E(2C_6))\), where
\(p=24\) and the \(2C_6\) are \(\{(x_{2,i}x_{3,i}x_{7,i}x_{4,i}x_{6,i}x_{8,i}x_{2,i})\),
\((x_{2,i}x_{5,i}x_{4,i}x_{8,i}x_{1,i}x_{6,i}x_{2,i})\}\),
\(1\leq i\leq 6\).
Proof. Let \(V(G=C_6 \Box (K_8\backslash E(2C_6))) = \left\{x_{i,j} : 1\leq i \leq 6, 1\leq j \leq 8 \right\}\). Since the degree of each vertex \(v\in V(G)\) is odd and \(\left|E(G)\right|=144\), then \(p=24\). Now, the 24\(P_7\) are given below: \(\{x_{i,1}x_{i+1,1}x_{i+1,5}x_{i+1,3}x_{i+1,8}x_{i+1,7}x_{i,7},\) \(x_{i,2}x_{i+1,2}x_{i+1,1}x_{i+1,3}x_{i+1,6}x_{i+1,5}x_{i,5}\), \(x_{i,3}x_{i+1,3}x_{i+1,4}x_{i+1,2}x_{i+1,7}\\x_{i+1,6}x_{i,6},\) \(x_{i,4}x_{i+1,4}x_{i+1,1}x_{i+1,7}x_{i+1,5}x_{i+1,8}x_{i,8}\), where \(1\leq i\leq 6\) and the first coordinate of subscripts of \(x\) are taken modulo \(6\) with residues \(\{1,\cdots,6 \}\}\). ◻
Lemma 3.17. There exists a \((6;p,q)\)-decomposition of \(K_8 \Box K_9\), \(p\geq 36\).
Proof. Since the degree of each vertex \(v\in V(K_8 \Box K_{9})\) is odd, then \(p\geq \frac{72}{2}=36\). For \(p=36\), the required number of \(P_7\)’s and \(C_6\)’s are constructed as follows:
\(\{x_{1,1}x_{1,3}x_{1,2}x_{6,2}x_{5,2}x_{3,2}x_{4,2},\
x_{1,2}x_{1,9}x_{1,7}x_{2,7}x_{3,7}x_{3,2}x_{6,2}\),
\(x_{5,7}x_{6,7}x_{6,1}x_{1,1}x_{7,1}x_{7,6}x_{7,3}\),
\(x_{1,5}x_{5,5}x_{6,5}x_{8,5}x_{8,2}x_{1,2}x_{3,2}\),
\(x_{1,6}x_{3,6}x_{3,2}x_{7,2}x_{1,2}x_{2,2}x_{2,4}\),
\(x_{1,7}x_{1,3}x_{2,3}x_{2,9}x_{2,5}x_{6,5}x_{6,3}\),
\(x_{1,8}x_{5,8}x_{5,6}x_{8,6}x_{8,9}x_{8,7}x_{7,7}\),
\(x_{1,9}x_{1,1}x_{2,1}x_{6,1}x_{8,1}x_{8,2}x_{8,8}\),
\(x_{2,1}x_{5,1}x_{1,1}x_{4,1}x_{4,2}x_{6,2}x_{8,2}\),
\(x_{2,2}x_{8,2}x_{8,4}x_{3,4}x_{2,4}x_{2,6}x_{2,7}\),
\(x_{2,3}x_{2,4}x_{6,4}x_{7,4}x_{7,6}x_{1,6}x_{6,6}\),
\(x_{2,5}x_{2,2}x_{4,2}x_{4,5}x_{3,5}x_{5,5}x_{8,5}\),
\(x_{2,6}x_{2,9}x_{2,4}x_{5,4}x_{5,1}x_{3,1}x_{7,1}\),
\(x_{2,8}x_{2,5}x_{2,7}x_{7,7}x_{5,7}x_{4,7}x_{4,6}\),
\(x_{2,9}x_{1,9}x_{7,9}x_{7,3}x_{8,3}x_{2,3}x_{4,3}\),
\(x_{3,1}x_{3,6}x_{7,6}x_{7,5}x_{7,1}x_{8,1}x_{8,9}\),
\(x_{3,3}x_{6,3}x_{4,3}x_{4,8}x_{3,8}x_{3,1}x_{4,1}\),
\(x_{3,4}x_{3,5}x_{3,3}x_{1,3}x_{8,3}x_{8,8}x_{7,8}\),
\(x_{3,5}x_{3,1}x_{3,7}x_{4,7}x_{4,3}x_{3,3}x_{3,6}\),
\(x_{3,7}x_{3,4}x_{4,4}x_{7,4}x_{5,4}x_{5,8}x_{5,9}\),
\(x_{3,8}x_{3,7}x_{8,7}x_{4,7}x_{4,5}x_{1,5}x_{7,5}\),
\(x_{4,4}x_{5,4}x_{5,3}x_{5,9}x_{6,9}x_{6,6}x_{6,1}\),
\(x_{4,5}x_{7,5}x_{3,5}x_{3,6}x_{6,6}x_{5,6}x_{5,4}\),
\(x_{4,7}x_{4,9}x_{4,4}x_{4,2}x_{4,8}x_{7,8}x_{7,6}\),
\(x_{4,8}x_{1,8}x_{1,2}x_{1,1}x_{1,4}x_{5,4}x_{6,4}\),
\(x_{4,9}x_{4,6}x_{2,6}x_{1,6}x_{8,6}x_{7,6}x_{7,2}\),
\(x_{5,3}x_{5,2}x_{5,9}x_{5,5}x_{5,8}x_{2,8}x_{6,8}\),
\(x_{5,5}x_{2,5}x_{1,5}x_{6,5}x_{6,2}x_{6,4}x_{6,7}\),
\(x_{5,6}x_{3,6}x_{4,6}x_{6,6}x_{8,6}x_{8,7}x_{8,3}\),
\(x_{5,8}x_{6,8}x_{7,8}x_{7,5}x_{6,5}x_{6,4}x_{6,9}\),
\(x_{6,5}x_{6,7}x_{6,6}x_{6,3}x_{5,3}x_{5,1}x_{8,1}\),
\(x_{7,4}x_{8,4}x_{8,9}x_{7,9}x_{7,5}x_{8,5}x_{8,7}\),
\(x_{8,4}x_{4,4}x_{1,4}x_{1,8}x_{2,8}x_{2,6}x_{8,6}\),
\(x_{7,9}x_{3,9}x_{4,9}x_{4,1}x_{7,1}x_{6,1}x_{5,1}\),
\(x_{1,4}x_{2,4}x_{7,4}x_{7,3}x_{7,2}x_{8,2}x_{5,2}\),
\(x_{1,3}x_{1,8}x_{1,9}x_{6,9}x_{8,9}x_{5,9}x_{3,9}\}\)
and
\(\left\{(\mathbf{x_{1,7}x_{1,2}}x_{1,6}x_{1,5}x_{1,1}x_{1,8}x_{1,7}),\
(x_{1,7}\mathbf{x_{1,4}x_{1,5}x_{1,3}x_{1,6}x_{1,1}x_{1,7}})\right\}\),
\(\left\{(\mathbf{x_{1,7}x_{3,7}}x_{6,7}x_{4,7}x_{2,7}x_{8,7}x_{1,7}),\
(x_{1,7}\mathbf{x_{1,6}x_{1,9}x_{1,4}x_{1,2}x_{1,5}x_{1,7}})\right\}\),
\(\left\{(x_{1,3}\mathbf{x_{1,4}x_{1,6}x_{1,8}x_{1,5}x_{1,9}x_{1,3}}),\
(\mathbf{x_{1,3}x_{6,3}}x_{8,3}x_{5,3}x_{3,3}x_{7,3}x_{1,3})\right\}\),
\(\left\{(\mathbf{x_{2,1}x_{2,2}x_{2,8}x_{2,3}x_{2,7}x_{2,9}}x_{2,1}),\
(x_{2,1}x_{2,7}x_{2,4}x_{2,5}x_{2,3}\mathbf{x_{2,6}x_{2,1}})\right\}\),
\(\left\{(x_{2,1}\mathbf{x_{2,4}x_{2,8}x_{2,9}x_{2,2}x_{2,3}x_{2,1}}),\
(x_{2,1}x_{2,8}x_{2,7}x_{2,2}x_{2,6}\mathbf{x_{2,5}x_{2,1}})\right\}\),
\(\left\{(x_{3,2}\mathbf{x_{3,8}x_{3,3}x_{3,7}x_{3,9}x_{3,1}x_{3,2}}),\
(\mathbf{x_{3,2}x_{3,5}}x_{3,7}x_{3,6}x_{3,9}x_{3,4}x_{3,2})\right\}\),
\(\left\{(\mathbf{x_{3,4}x_{3,8}x_{3,9}x_{3,2}x_{3,3}x_{3,1}}x_{3,4}),\
(\mathbf{x_{3,4}x_{3,6}}x_{3,8}x_{3,5}x_{3,9}x_{3,3}x_{3,4})\right\}\),
\(\left\{(\mathbf{x_{4,4}x_{4,6}x_{4,8}}x_{4,5}x_{4,9}x_{4,3}x_{4,4}),\
(\mathbf{x_{4,4}x_{4,5}x_{4,3}x_{4,6}x_{4,1}}x_{4,7}x_{4,4})\right\}\),
\(\left\{(x_{4,9}\mathbf{x_{4,2}x_{4,3}x_{4,1}x_{4,4}x_{4,8}x_{4,9}}),\
(\mathbf{x_{4,9}x_{5,9}}x_{7,9}x_{2,9}x_{3,9}x_{8,9}x_{4,9})\right\}\),
\(\left\{(\mathbf{x_{4,8}x_{4,7}x_{4,2}x_{4,6}x_{4,5}x_{4,1}}x_{4,8}),\
(\mathbf{x_{4,8}x_{2,8}}x_{8,8}x_{1,8}x_{3,8}x_{6,8}x_{4,8})\right\}\),
\(\left\{(x_{5,2}\mathbf{x_{5,8}x_{5,3}x_{5,7}x_{5,9}x_{5,1}x_{5,2}}),\
(\mathbf{x_{5,2}x_{5,5}}x_{5,7}x_{5,6}x_{5,9}x_{5,4}x_{5,2})\right\}\),
\(\left\{(x_{5,5}\mathbf{x_{5,1}x_{5,8}x_{5,7}x_{5,2}x_{5,6}x_{5,5}}),\
(\mathbf{x_{5,5}x_{5,3}}x_{5,6}x_{5,1}x_{5,7}x_{5,4}x_{5,5})\right\}\),
\(\left\{(\mathbf{x_{6,2}x_{6,8}x_{6,3}x_{6,7}x_{6,9}}x_{6,1}x_{6,2}),\
(\mathbf{x_{6,2}x_{6,6}x_{6,5}}x_{6,1}x_{6,8}x_{6,7}x_{6,2})\right\}\),
\(\left\{(x_{6,4}\mathbf{x_{6,6}x_{6,8}x_{6,5}x_{6,9}x_{6,3}x_{6,4}}),\
(x_{6,4}x_{6,8}x_{6,9}x_{6,2}x_{6,3}\mathbf{x_{6,1}x_{6,4}})\right\}\),
\(\left\{(x_{7,2}\mathbf{x_{7,8}x_{7,3}x_{7,7}x_{7,9}x_{7,1}x_{7,2}}),\
(\mathbf{x_{7,2}x_{7,5}}x_{7,7}x_{7,6}x_{7,9}x_{7,4}x_{7,2})\right\}\),
\(\left\{(\mathbf{x_{7,7}x_{7,1}x_{7,4}x_{7,8}x_{7,9}}x_{7,2}x_{7,7}),\
(\mathbf{x_{7,7}x_{7,4}x_{7,5}}x_{7,3}x_{7,1}x_{7,8}x_{7,7})\right\}\),
\(\left\{(\mathbf{x_{8,6}x_{8,8}x_{8,5}x_{8,9}x_{8,3}x_{8,4}}x_{8,6}),\
(x_{8,6}x_{8,5}x_{8,1}x_{8,8}x_{8,7}\mathbf{x_{8,2}x_{8,6}})\right\}\),
\(\left\{(\mathbf{x_{8,3}x_{8,1}x_{8,4}x_{8,8}x_{8,9}x_{8,2}}x_{8,3}),\
(\mathbf{x_{8,3}x_{8,6}}x_{8,1}x_{8,7}x_{8,4}x_{8,5}x_{8,3})\right\}\),
\(\left\{(\mathbf{x_{3,1}x_{6,1}x_{4,1}x_{2,1}x_{8,1}}x_{1,1}x_{3,1}),\
(x_{3,1}x_{8,1}x_{4,1}x_{5,1}\mathbf{x_{7,1}x_{2,1}x_{3,1}})\right\}\),
\(\left\{(\mathbf{x_{7,2}x_{6,2}x_{2,2}x_{5,2}x_{1,2}}x_{4,2}x_{7,2}),\
(\mathbf{x_{7,2}x_{2,2}x_{3,2}}x_{8,2}x_{4,2}x_{5,2}x_{7,2})\right\}\),
\(\left\{(\mathbf{x_{2,3}x_{5,3}x_{1,3}x_{4,3}x_{7,3}x_{6,3}}x_{2,3}),\
(\mathbf{x_{2,3}x_{3,3}}x_{8,3}x_{4,3}x_{5,3}x_{7,3}x_{2,3})\right\}\),
\(\left\{(x_{1,4}\mathbf{x_{6,4}x_{8,4}x_{5,4}x_{3,4}x_{7,4}}x_{1,4}),\
(x_{1,4}x_{3,4}\mathbf{x_{6,4}x_{4,4}x_{2,4}}x_{8,4}x_{1,4})\right\}\),
\(\left\{(\mathbf{x_{1,5}x_{3,5}x_{6,5}x_{4,5}x_{2,5}}x_{8,5}x_{1,5}),\
(x_{2,5}x_{3,5}x_{8,5}x_{4,5}\mathbf{x_{5,5}x_{7,5}x_{2,5}})\right\}\),
\(\left\{(\mathbf{x_{1,6}x_{4,6}x_{7,6}x_{6,6}x_{2,6}}x_{5,6}x_{1,6}),\
(\mathbf{x_{2,6}x_{3,6}x_{8,6}}x_{4,6}x_{5,6}x_{7,6}x_{2,6})\right\}\),
\(\left\{(\mathbf{x_{5,7}x_{1,7}x_{4,7}x_{7,7}x_{6,7}x_{2,7}}x_{5,7}),\
(\mathbf{x_{5,7}x_{3,7}}x_{7,7}x_{1,7}x_{6,7}x_{8,7}x_{5,7})\right\}\),
\(\left\{(\mathbf{x_{2,8}x_{3,8}x_{8,8}x_{4,8}x_{5,8}x_{7,8}}x_{2,8}),\
(x_{1,8}x_{6,8}x_{8,8}x_{5,8}x_{3,8}\mathbf{x_{7,8}x_{1,8}})\right\}\),
\(\left\{(x_{1,9}\mathbf{x_{3,9}x_{6,9}x_{4,9}x_{2,9}x_{8,9}x_{1,9}}),\
(x_{1,9}x_{4,9}x_{7,9}x_{6,9}x_{2,9}\mathbf{x_{5,9}x_{1,9}})\right\}\).
For \(p=37\), we decompose the last path and first cycle into \(2P_7\) as follows: \[\left\{x_{1,7}x_{1,2}x_{1,6}x_{1,5}x_{1,1}x_{1,8}x_{1,3},\ x_{1,7}x_{1,8}x_{1,9}x_{6,9}x_{8,9}x_{5,9}x_{3,9}\right\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from \(C_6\)’s for \(p>37\). So, we have the desired decomposition for \(K_8 \Box K_{9}\). ◻
Theorem 3.18. \(K_m \Box K_n\) has a \((6;p,q)\)-decomposition if and only if \(mn(m+n-2)\equiv\,0\,\pmod {12}\).
Proof. Necessity. Since \(K_m \Box K_n\) is \((m+n-2)\)-regular with \(mn\) vertices, \(K_m \Box K_n\) has \(mn(m+n-2)/2\) edges. Now, assume that \(K_m \Box K_n\) has a \((6;p,q)\)-decomposition. Then the number of
edges in the graph must be divisible by 6, i.e., \(12| mn(m+n-2)\) and hence \(mn(m+n-2) \equiv\,0\,\pmod {12}\).
Sufficiency. We construct the required decomposition in
ten cases.
Case 1. \(m\equiv\,0\,\pmod {6}\) and \(n\equiv\,0\,\pmod {2}\).
Subcase 1.1. \(m, n\equiv\,0\,\pmod {6}\) .
Let \(m=6k\) and \(n=6l\), where \(k,l > 0\) are integers. We can write \(K_m \Box K_n = kl(K_6 \Box K_6)\ \oplus\ 3kl (k+l-2) K_{6,6}\). By Theorem 1.2 and Lemma 3.8, \(K_{6,6}\) and \(K_6 \Box K_6\) have a \((6;p,q)\)-decomposition. Hence by Remark 1.3, \(K_m \Box K_n\) has a \((6;p,q)\)-decomposition.
Subcase 1.2. \(m\equiv\,0\,\pmod {6},\ n\equiv\,4\,\pmod {6}\) .
Let \(m=6k\) and \(n=6l+4\), where \(k,l\) are non-negative integers. We can write \(K_m \Box K_n = (K_{6k} \Box K_{6l})\ \oplus\ k(K_6 \Box K_4)\ \oplus\ 2k(k-1) K_{6,6}\ \oplus\ 6kK_{6l,4}\). By Theorem 12, Lemmas 3.7, and 2.4, Subcase 1.1 and Remark 1.3, \(K_m \Box K_n\) has a \((6;p,q)\)-decomposition.
Subcase 1.3. \(m\equiv\,0\,\pmod {6},\ n\equiv\,2\,\pmod {6}\) .
When \(m=6k\) and \(n=2\), \(K_m \Box K_n = k (K_6 \Box K_2)\ \oplus\ k(k-1)K_{6,6}\). By Theorem 1.2, Lemma 3.6 and Remark 1.3, \(K_m \Box K_n\) has a \((6;p,q)\)-decomposition. When \(m=6k\) and \(n=8\), \(K_m \Box K_n = k (K_6 \Box K_8)\ \oplus\ 4k(k-1)K_{6,6}\). By Theorem 1.2, Lemma 3.9 and Remark 1.3, \(K_m \Box K_n\) has a \((6;p,q)\)-decomposition. When \(n>8\), let \(m=6k,\ n=6l+8\), where \(k,l\) are non-negative integers. We can write \(K_m \Box K_n = (K_{6k} \Box K_{6l})\ \oplus\ (K_{6k} \Box K_8)\ \oplus\ 6kK_{6l,8}\). By Theorem 1.2, Lemma 2.4, Subcase 1.1 and Remark 1.3, \(K_m \Box K_n\) has a \((6;p,q)\)-decomposition.
Case 2. \(m, n\equiv\,4\,\pmod {6}\).
Let \(m=6k+4\) and \(n=6l+4\), where \(k,l\) are non-negative integers. We can write \(K_m \Box K_n = kl (K_6 \Box K_6)\ \oplus\ (k+l)(K_6 \Box K_4)\ \oplus\ (K_4 \Box K_4)\ \oplus\ (3kl (k+l-2)+2k(k-1)) K_{6,6}\ \oplus\ (12kl+4(l+k))K_{6,4}\). By Theorem 1.2, Lemmas 3.7, 3.8, 3.10 and 2.4 and Remark 1.3, \(K_m \Box K_n\) has a \((6;p,q)\)-decomposition.
Case 3. \(m\equiv\, 0,1,4\ or\ 9\,\pmod {12}\), \(n\equiv\, 1\ or\ 9\,\pmod {12}\).
When \(m\) is even, the degree of each vertex \(v\in V(K_m \Box K_n)\) is odd, then \(p\geq mn/2\). Now, \(K_m \Box K_n = nK_m\ \oplus\ mK_n\). By Lemma 2.8 and Theorem 1.1, \(K_m\) and \(K_n\) have a \((6;p,q)\)-decomposition (with \(p\geq m/2\) whenever \(m\) is even). Hence by Remark 1.3, \(K_m \Box K_n\) has the required decomposition.
Case 4. \(m, n\equiv 3\ or\ 7\,\pmod {12}\).
Subcase 4.1. \(m, n\equiv\, i\,\pmod {12}\), \(i=3,7\).
When \(m =n\), if \(i =3\), then \(K_m \Box K_n = nK_m\ \oplus\ mK_n = 2m(K_m\backslash E(K_3))\ \oplus\ \frac{m}{3} (K_3 \Box K_3)\). If \(i=7\) let \(m=12k+7\), then \(K_m \Box K_n = 2(m-7)(K_m\backslash E(K_3))\ \oplus\ \frac{(m-7)}{3} (K_3 \Box K_3)\ \oplus\ 14(K_{12k+1} \oplus K_{12k,6})\ \oplus\ K_7 \Box K_7\). By Lemmas 2.6,3.1, 3.11, Theorems 1.1, 1.2 and Remark 1.3, \(K_m \Box K_n\) has a \((6;p,q)\)-decomposition.
When \(m<n\), let \(n=m+h\), where \(h=12l, l \in \mathbb{Z} ^+\ m=12k+i\), \(i=3,7\). We can write \(K_m \Box K_n=(K_m \Box K_m)\ \oplus\ hK_m\ \oplus\ m(K_n\backslash E(K_m))=(K_m \Box K_m)\ \oplus\ 12l(K_m\backslash E(K_3))\ \oplus\ 12lK_3\ \oplus\ m(K_{12l+1}\ \oplus\ K_{12l,m-1})\). Now, the first three rows of \((K_m \Box K_n)\backslash (K_m \Box K_m)\) can be viewed as \((K_{12l+1}\backslash E(2lC_6))\ \oplus\ K_{12l,m-1}\ \oplus\ 2lC_6\). As in the proof of Lemma 3.12, we can prove \(12lK_{3}\) along with three rows of \(2lC_6\) has a \((6;p,q)\)-decomposition. By Lemmas 2.4 and 2.5 and Theorem 1.2, \(K_{12l+1}\backslash E(2lC_6)\) and \(K_{12l,m-1}\) have a \((6;p,q)\)-decomposition. Hence by Remark 1.3, \(K_m \Box K_n\) has a \((6;p,q)\)-decomposition.
Subcase 4.2. \(m\equiv\, 3\,\pmod {12},\ n\equiv\,7\,\pmod {12}\).
Let \(m=12k+3, n=12l+7\). We can write \(K_m \Box K_n=nK_m\ \oplus\ mK_n\).
When \(k=l\), every column of \(K_m \Box K_n\) can be viewed as \((K_m\backslash E(K_3))\ \oplus\ K_3\) and every first \((m-3)\) rows can be viewed as \((K_n\backslash E(K_3))\ \oplus\ K_3\) and last three rows can be viewed as \((K_n\backslash E(K_7))\ \oplus\ K_7\). Now, the \(K_3\)’s in first \((m-3)\) rows and columns form \(\frac{(m-3)}{3}(K_3 \Box K_3)\) and \(K_n\backslash E(K_7)\) can be viewed as \(K_{12l+1}\ \oplus\ K_{12l,6}\) and these graphs have a \((6; p, q)\)-decomposition, by Theorems 1.1, 1.2. By Lemmas 2.6 and 3.1, \(K_m\backslash E(K_3), K_n\backslash E(K_3)\) and \((K_3 \Box K_3)\) have a \((6;p,q)\)-decomposition. By Lemma 3.2, the remaining graph \(K_3 \Box K_7\) has a \((6;p,q)\)-decomposition.
When \(k<l\), every column of \(K_m \Box K_n\) can be viewed as \((K_m\backslash E(K_3))\ \oplus\ K_3\) and every first \((m-3)\) rows can be viewed as \((K_n\backslash E(K_3))\ \oplus\ K_3\). Now, the \(K_3\)’s in first \((m-3)\) rows and columns form \(\frac{(m-3)}{3}(K_3 \Box K_3)\). By Lemmas 2.6 and 3.1, \(K_m\backslash E(K_3), K_n\backslash E(K_3)\) and \((K_3 \Box K_3)\) have a \((6;p,q)\)-decomposition. Finally, we have to find a \((6;p,q)\)-decomposition of the last three rows and \(12(l-k)+7\) columns of \(K_m \Box K_n\). Now, every \(12(l-k)+7\) columns of \(K_m \Box K_n\) can be viewed as \((K_m\backslash E(K_3))\ \oplus\ (K_m\backslash V(K_{m-3}))\) and every last three rows of \(K_m \Box K_n\) can be viewed as \(K_{12k+1}\ \oplus\ K_7\ \oplus\ K_{12k,6}\ \oplus\ K_{12(l-k),6}\ \oplus\ K_{12k,12(l-k)}\ \oplus\ (K_{12(l-k)+1}\backslash E(2(l-k)C_6))\ \oplus\ 2(l-k)C_6\) and by Theorem 1.2, \(K_{12k,6}\ \oplus\ K_{12(l-k),6}=K_{12l,6}\) has a \((6;p,q)\)-decomposition. By Lemma 2.5, \(K_{12(l-k)+1}\backslash E(2(l-k)C_6)\) has a \((6;p,q)\)-decomposition. As in the proof of Lemma 3.2, we can prove \(12(l-k)K_n\backslash V(K_{n-3})\) along with the three rows of \(2(l-k)C_6\) has a \((6;p,q)\)-decomposition. By Lemma 3.2, the remaining graph \(K_3 \Box K_7\) has a \((6;p,q)\)-decomposition.
By using similar proof, we can prove for the case \(k>l\) also. Hence \(K_m \Box K_n\) has a \((6;p,q)\)-decomposition.
Case 5. \(m\equiv\, 3\,\pmod {12},\ n\equiv\, 11\,\pmod {12}\).
Let \(m=12k+3, n=12l+11\). We can write \(K_m \Box K_n=nK_m\ \oplus\ mK_n\). Consider all columns as \((K_m\backslash E(K_3))\ \oplus\ K_3\) except the columns 1, 3, 4 and 7 and consider these columns as \((K_m\backslash (E(K_3))\ \oplus\ E(2kC_6))\oplus K_3\ \oplus\ 2kC_6\) and all rows can be viewed as \((K_n\backslash E(C_7))\ \oplus\ C_7\) except the last three rows. The last three rows can be viewed as \((K_{12l+1}\backslash E(2lC_6))\ \oplus\ K_{12l,10}\ \oplus\ 2lC_6\ \oplus\ K_{11}\). In each column \(K_m\backslash E(K_3)\) has a \((6;p,q)\)-decomposition and in columns 1, 3, 4 and 7 the graph \((K_m\backslash (E(K_3))\ \oplus\ E(2kC_6))\) has a \((6;p,q)\)-decomposition, by Lemma 2.6. So the remaining edges in columns 1, 3, 4 and 7 form \(K_3\oplus 2kC_6\) and in other columns form \(K_3\). By Lemma 2.7 and Theorem 1.1, the graphs \(K_n\backslash E(C_7)\) and \(K_{12l+1}\) have a \((6;p,q)\)-decomposition and \(K_{12l,10}=2l(K_{6,6}\ \oplus\ K_{6,4})\) has a \((6;p,q)\)-decomposition, by Theorem 1.2 and Lemma 2.4. So the remaining edges in the first \((m-3)\) rows form \(12kC_7\) and in the last three rows form \(K_{11}\oplus 2lC_6\). The graph \(12l K_3\) in the first \(12l\) columns along with \(2lC_6\) in the last three rows have a \((6;p,q)\)-decomposition as in Lemma 3.12. Also, the edges of \(12kC_7\) along with four columns of \(2kC_6\) can have a \((6;p,q)\)-decomposition as in Lemma 3.15.
Now, the remaining edges (\(K_3\)’s) in the last 11 columns and (\(K_{11}\)’s) in the last 3 rows will form \(K_3\Box K_{11}\) which has a \((6;p,q)\)-decomposition, by Lemma 3.4. Hence by Remark 1.3 \(K_m \Box K_n\) has a \((6;p,q)\)-decomposition.
Case 6. \(m\equiv\, 5\,\pmod {12},\ n\equiv\, 9\,\pmod {12}\).
Let \(m=12k+5,\ n=12l+9\). We can write \(K_m \Box K_n=nK_m\ \oplus\ mK_n=n((K_m\backslash E(C_4))\ \oplus\ C_4)\ \oplus\ mK_n\). Consider the first 5 rows and the last 2 rows as \(K_{12l+1}\ \oplus\ K_9\ \oplus\ K_{12,8}\) and \((K_{12l+1}\backslash E(2lC_6))\ \oplus\ 2lC_6\ \oplus\ K_9\oplus K_{12,8}\) respectively. The graph \((n-9)C_4\) in the first \(n-9\) columns along with the last 2 rows of \(2lC_6\) can be viewed as \(2lG\), where \(G=6C_4\ \oplus\ 2C_6= C_4^1\ \oplus\ C_4^2\ \oplus\ \cdots\ \oplus\ C_4^6\ \oplus\ C_6^3\ \oplus\ C_6^4\) with \(V(G)=\left\{x_{i,j} | 1\leq i\leq 4, \leq j\leq 2\right\}\) and \(C_4^i=(x_{1,i}x_{2,i}x_{3,i}x_{4,i}x_{1,i}),\ 1\leq i\leq 6,\ C_6^j=(x_{j,1}x_{j,2}x_{j,3}x_{j,4}x_{j,5}x_{j,6}x_{j,1}),\ j=3,4\) and \(G\) can be decomposed into \(C_6\)’s as follows: \[\left\{(x_{3,2i}\mathbf{x_{3,(2i-1)}x_{2,(2i-1)}x_{1,(2i-1)}x_{4,(2i-1)}x_{4,2i}x_{3,2i}})\right., \left.(\mathbf{x_{3,2i}x_{2,2i}}x_{1,2i}x_{4,2i}x_{4,(2i+1)}x_{3,(2i+1)}x_{3,2i})\right\},\] where \(1\leq i\leq 6\) and the subscripts of \(x\) are taken modulo 6 with residues \(\{1,\cdots,6\}\). The first three cycles can be decomposed into 3\(P_7\) as follows: \(\{x_{1,2}x_{4,2}x_{4,1}x_{1,1}x_{2,1}x_{3,1}x_{3,2}\), \(x_{3,2}x_{4,2}x_{4,3}x_{1,3}x_{2,3}x_{3,3}x_{3,4}\), \(x_{3,4}x_{4,4}x_{4,3}x_{3,3}x_{3,2}x_{2,2}x_{1,2}\}\). Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)-decomposition of \(G\) given above. By Theorem 1.1, Lemmas 2.3, 2.4 and 2.5, \(K_n\), \(K_{12l+1}\backslash E(2kC_6),\ K_9\) and \(K_{12,8}\) have a \((6;p,q)\)-decomposition. Now, consider the remaining 9\(C_4\) with 5\(C_6\) from the first 5 rows in \(5\times 9\) block with vertex and edge set as follows: \[V(G)=\left\{x_{i,j} | 1\leq i\leq 5, \leq j\leq 6\right\}\] and \[C_4^i=(x_{1,i}x_{2,i}x_{3,i}x_{4,i}x_{1,i}), i=3,4,8\] and \[\begin{aligned} &C_4^1=(x_{1,1}x_{2,1}x_{4,1}x_{3,1}x_{1,1}),\\ & C_4^2=(x_{2,2}x_{3,2}x_{4,2}x_{5,2}x_{2,2}),\\ &C_4^5=(x_{1,5}x_{3,5}x_{5,5}x_{4,5}x_{1,5}), \\ &C_4^6=(x_{1,6}x_{4,6}x_{2,6}x_{3,6}x_{1,6}),\\ &C_4^7=(x_{1,7}x_{3,7}x_{5,7}x_{2,7}x_{1,7}),\\ & C_4^9=(x_{1,9}x_{4,9}x_{3,9}x_{5,9}x_{1,9}),\\ &C_6^1=(x_{1,1}x_{1,3}x_{1,5}x_{1,7}x_{1,9}x_{1,8}x_{1,1}),\\ & C_6^2=(x_{2,1}x_{2,2}x_{2,3}x_{2,6}x_{2,7}x_{2,8}x_{2,1}),\\ &C_6^3=(x_{3,1}x_{3,3}x_{3,4}x_{3,6}x_{3,5}x_{3,2}x_{3,1}),\\ & C_6^4=(x_{4,2}x_{4,3}x_{4,4}x_{4,7}x_{4,6}x_{4,9}x_{4,2}),\\ &C_6^5=(x_{5,2}x_{5,3}x_{5,5}x_{5,7}x_{5,9}x_{5,4}x_{5,2}). \end{aligned}\]
Now, this \(G\) can be decomposed into \(C_6\)’s as follows:
\[\begin{aligned} &\left\{(x_{1,8}\mathbf{x_{1,9}x_{5,9}x_{5,7}x_{2,7}x_{2,8}x_{1,8}}),\ (\mathbf{x_{1,8}x_{4,8}}x_{3,8}x_{2,8}x_{2,1}x_{1,1}x_{1,8})\right\},\\ &\left\{(x_{5,5}\mathbf{x_{4,5}x_{1,5}x_{1,7}x_{3,7}x_{5,7}x_{5,5}}),\ (\mathbf{x_{5,5}x_{5,3}}x_{5,2}x_{2,2}x_{3,2}x_{3,5}x_{5,5})\right\},\\ &\left\{(x_{3,3}\mathbf{x_{2,3}x_{2,2}x_{2,1}x_{4,1}x_{3,1}x_{3,3}}),\ (\mathbf{x_{3,3}x_{3,4}}x_{2,4}x_{1,4}x_{4,4}x_{4,3}x_{3,3})\right\},\\ &\left\{(x_{4,2}\mathbf{x_{3,2}x_{3,1}x_{1,1}x_{1,3}x_{4,3}x_{4,2}}),\ (\mathbf{x_{4,2}x_{5,2}}x_{5,4}x_{5,9}x_{3,9}x_{4,9}x_{4,2})\right\},\\ &\left\{(x_{4,6}\mathbf{x_{4,7}x_{4,4}x_{3,4}x_{3,6}x_{1,6}x_{4,6}}),\ (\mathbf{x_{4,6}x_{2,6}}x_{2,7}x_{1,7}x_{1,9}x_{4,9}x_{4,6})\right\},\\ &(x_{1,3}x_{2,3}x_{2,6}x_{3,6}x_{3,5}x_{1,5}x_{1,3}). \end{aligned}\]
The last 3\(C_6\) can be decomposed into 3\(P_7\) as follows: \[\{x_{1,3}x_{2,3}x_{2,6}x_{4,6}x_{4,9}x_{1,9}x_{1,7}, x_{1,7}x_{2,7}x_{2,6}x_{3,6}x_{1,6}x_{4,6}x_{4,7}, x_{4,7}x_{4,4}x_{3,4}x_{3,6}x_{3,5}x_{1,5}x_{1,3}\}.\]
Now, using Construction 1.4 we get the required number of paths and cycles from the \(C_6\)-decomposition of \(G\) given above. Hence we have the desired decomposition of \(K_m\Box K_n\).
Note 3.19. From Case 7 to Case 10 the degree of each vertex \(v\in V(K_m \Box K_n)\) is odd and so \(p\geq mn/2\).
Case 7. \(m\equiv\, 0\,\pmod {12}\), \(n\equiv\, i\,\pmod {12}\), \(i=3,5,7,11\).
Let \(m=12k\) and \(n=12l+i\), \(l,k\in Z^+\) and \(i\in \left\{3,5,7,11\right\}\). We can write \(K_m \Box K_n=nK_m\ \oplus\ mK_n=(n-i)K_m\ \oplus\ k(K_i \Box K_{12})\ \oplus\ i\frac{k(k-1)}{2} K_{12,12}\ \oplus\ m(K_n\backslash E(K_i))\), \(i\in \left\{3,5,7,11\right\}\). By Lemma 2.6, \(K_n\backslash E(K_i)\) has a \((6;p,q)\)-decomposition for \(i=3\). For \(i\in \left\{5,7,11\right\}\), \(K_n\backslash E(K_i)\) can be viewed as \(K_{12l+1}\oplus K_{12l,i-1}\) and these graphs have a \((6;p,q)\)-decomposition, by Theorems 1.1, 1.2 and Lemma 2.4. Also by Theorem 1.2 and Lemmas 3.12 to 3.15, \(K_{12,12}\) and \(K_i \Box K_{12}\), \(i\in \left\{3,5,7,11\right\}\) have a \((6;p,q)\)-decomposition. Hence by Remark 1.3, \(K_m \Box K_n\) has a \((6;p,q)\)-decomposition.
Case 8. \(m\equiv\, 4\,\pmod {12},\ n\equiv\, 3\ or\ 7\,\pmod {12}\).
Let \(m=12k+4\). Then \(K_m \Box K_n = nK_m\ \oplus\ mK_n = nK_m\ \oplus\ m((K_n\backslash E(K_3))\) \(\oplus K_3)\). By Lemmas 2.6 and 2.8, \(K_m\) has a \((6; p, q)\)-decomposition with \(p \geq m/2\) and \(K_n\backslash E(K_3)\) has a \((6;p,q)\)-decomposition. Now, the last three columns can be viewed as \((K_{12(k-1)}\backslash E(2(k-1)C_6))\oplus 2(k-1)C_6\ \oplus\ K_{16}\ \oplus\ K_{12(k-1),16}\). By Lemmas 2.5 and 2.4, \(K_{12(k-1)}\backslash E(2(k-1)C_6)\) and \(K_{12(k-1),16}\) have a \((6;p,q)\)-decomposition. The graph \(12(k-1)K_3\) in the first \(12(k-1)\) rows along with the last 3 columns of \(2(k-1)C_6\) can be viewed as \(2(k-1)(6K_3\oplus 3C_6)\). We can prove this has a \((6;p,q)\)-decomposition as in Lemma 3.12. Now, \(K_{16}\)’s of last 3 columns and \(K_3\)’s of last 16 rows form \(K_3 \Box K_{16}\) and this has a \((6;p,q)\)-decomposition, by Lemma 3.5.
Case 9. \(m\equiv\,8\,\pmod {12},\ n\equiv\,3\,\pmod {12}\).
Let \(m=12k+8\) and \(n=12l+3\). We can write \(K_m \Box K_n = nK_m\ \oplus\ mK_n=n((K_{12k}\ \oplus\ 2C_6)\ \oplus\ (K_8\backslash E(2C_6))\ \oplus\ K_{12k,8})\ \oplus\ m((K_n\backslash E(K_3))\oplus K_3)\), where \(2C_6\) are \((x_{2,i}x_{3,i}x_{7,i}x_{4,i}x_{6,i}x_{8,i}x_{2,i}),\\ (x_{2,i}x_{5,i}x_{4,i}x_{8,i}x_{1,i}x_{6,i}x_{2,i})\), \(1\leq i\leq n\). Last three columns can be viewed as \((K_{12k}\backslash E(2kC_6))\ \oplus\ 2kC_6\ \oplus\ K_8\ \oplus\ K_{12k,8}\) and first three rows can be viewed as \((K_m\backslash E(2lC_6\ \oplus\ K_3))\ \oplus\ 2lC_6\ \oplus K_3\). The graph \(12kK_3\) in the last \(12k\) rows along with the last 3 columns of \(2kC_6\) can be viewed as \(2k(6K_3\ \oplus\ 3C_6)\). We can prove this has a \((6;p,q)\)-decomposition as in Lemma 3.12. Now, \(K_8\)’s in last three columns and \(K_3\)’s in the first 8 rows forms \(K_8 \Box K_3\) and by Lemma 3.3, which has a \((6;p,q)\)-decomposition. Also by Lemma 2.8, \(K_{12k}\oplus 2C_6\) in the first \((n-3)\) columns has a \((6;p,q)\)-decomposition. The remaining edges \(K_8\backslash E(2C_6)\) in the first \(12l\) columns and \(2lC_6\) in first 3 rows form \((K_8\backslash E(2C_6)) \Box C_6\) which has a \((6;p,q)\)-decomposition, by Lemma 3.16.
Case 10. \(m\equiv\,8\,\pmod {12},\ n\equiv\,9\,\pmod {12}\).
Let \(m=12k+8\) and \(n=12l+9\). We can write \(K_m \Box K_n = nK_m\ \oplus\ mK_n = (n-9) ((K_{12k}\ \oplus\ 2C_6)\ \oplus\ (K_8\backslash E(2C_6))\ \oplus\ K_{12k,8})\ \oplus\ 9(K_{12k}\ \oplus\ K_8\ \oplus\ K_{12k,8})\ \oplus\ mK_n\). The last 8 rows can be viewed as \(K_{12l+1}\backslash E(2lC_6)\ \oplus\ 2lC_6\ \oplus\ K_9\ \oplus\ K_{12l,8}\). Now, the graph \(K_8\backslash E(2C_6)\) in each \((n-9)\) columns along with \(2lC_6\) in last 8 rows forms \(2l((K_8\backslash E(2C_6)) \Box C_6)\) which has a \((6;p,q)\)-decomposition, by Lemma 3.16 and the graph \(K_8\)’s in last 9 columns and \(K_9\)’s in last 8 rows will form \(K_8 \Box K_9\) which has a \((6;p,q)\)-decomposition, by Lemma 3.17. By Lemmas 2.4, 2.5 and 2.8, the remaining edges have a \((6;p,q)\)decomposition.
◻
The authors thank the Department of Science and Technology, Government of India, New Delhi for its financial support through the Grant No. DST/ SR/ S4/ MS:828/13. The second author thank the University Grant Commission for its support through the Grant No. F.510/7/DRS-I/2016(SAP-I).