Decomposition of the cartesian product of complete graphs into paths and cycles of length six

Ezhilarasi, A. Pauline; Muthusamy, A.

doi:10.61091/jcmcc124-39

Abstract

1. Introduction
2. Base Constructions
3. (6;p,q)-decomposition of KmKn
Acknowledgement:

References

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume 124
Pages: 581-600

Research article

Decomposition of the cartesian product of complete graphs into paths and cycles of length six

^¹, ^²

¹Department of Mathematics, Jeppiaar Engineering College, Chennai-600119, India

²Department of Mathematics, Periyar University, Salem-636011, India

Accepted: 04/06/2020
Published Online: 19/03/2025

Copyright Link
License

Abstract

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 ${P_{7}, C_{6}}$ -decomposition of the cartesian product of complete graphs.

Keywords: graph decomposition, path, cycle and product graph

1. Introduction

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}, \dots, n_{m}}$ , when $| V_{i} | = n_{i}$ for all $i$ . For $G = K_{2 n}$ or $K_{n, n}$ , the graph $G - I$ denotes the graph G with a $1$ -factor $I$ removed. For any integer $λ > 0$ , $λ G$ denotes $λ$ edge-disjoint copies of $G$ . The complement of the graph $G$ is denoted by $\bar{G}$ . For two graphs $G$ and $H$ we define their $C a r t e s i a n$ $p r o d u c t$ , denoted by $G H$ , as follows: the vertex set is $V (G) \times V (H)$ and its edge set is

$E (G H) = {(g, h) (g^{'}, h^{'}) : g = g^{'}, h h^{'} \in E (H), o r g g^{'} \in E (G), h = h^{'}} .$

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}, \dots, H_{k}$ such that $E (G) = E (H_{1}) \cup \dots \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} ≅ 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 ${p H_{1}, q H_{2}}$ -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 ${H_{1}, H_{2}}_{{p, q}}$ -decomposition or complete ${H_{1}, H_{2}}$ -decomposition.

The study of ${H_{1}, H_{2}}_{{p, q}}$ -decomposition of graphs is not new. Authors in [2,4] completely determined the values of $n$ for which $K_{n} (λ)$ admits a ${p H_{1}, q H_{2}}$ -decomposition such that $H_{1} \cup H_{2} ≅ K_{t}$ , when $λ \geq 1$ and $| V (H_{1}) | = | V (H_{2}) | = t$ , when $t \in {4, 5}$ . Abueida and Daven [3] proved that there exists a ${p K_{k}, q S_{k + 1}}$ -decomposition of $K_{n}$ , for $k \geq 3$ and $n \equiv 0, 1 (m o d k)$ . Abueida and O’Neil [1] proved that for $k \in {3, 4, 5}$ , there exists a ${p C_{k}, q S_{k}}$ -decomposition of $K_{n} (λ)$ , whenever $n \geq k + 1$ except for the ordered triples $(k, n, λ) \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} K_{n}$ . Fu et al. [8] established necessary and sufficient condition for the existence of ${C_{3}, S_{4}}_{{p, q}}$ -decomposition of $K_{n}$ . Shyu [12] obtained a necessary and sufficient condition on ${p, q}$ for the existence of ${P_{5}, C_{4}}_{{p, q}}$ -decomposition of $K_{n}$ . Priyadharsini and Muthusamy [11] established necessary and sufficient condition for the existence of the ${p G_{n}, q H_{n}}$ -decomposition of $K_{n} (λ)$ when $G_{n}, H_{n} \in {C_{n}, P_{n - 1}, S_{n - 1}}$ . Jeevadoss and Muthusamy [9] obtained some necessary and sufficient conditions for the existence of ${P_{k + 1}, C_{k}}_{{p, q}}$ -decomposition of $K_{m, n}$ . Jeevadoss and Muthusamy [10] obtained necessary and sufficient conditions for the existence of ${P_{5}, C_{4}}_{{p, q}}$ -decomposition of $K_{m} \times K_{n}$ , $K_{m} \otimes \bar{K_{n}}$ and $K_{m} 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 $m n (m + n - 2) \equiv 0 (\mod 12)$ is sufficient for the existence of a ${P_{7}, C_{6}}_{{p, q}}$ -decomposition of $K_{m} K_{n}$ . We abbreviate the ${P_{k + 1}, C_{k}}_{{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 > 4 k$ be an odd integer. If $k (p + q) = (\binom{n}{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_{s k, t k}$ 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_{0} x_{1} x_{2} x_{3} x_{4} x_{5} x_{0})$ and $C_{6}^{2} = (y_{0} y_{1} y_{2} y_{3} y_{4} y_{5} y_{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} - v x_{i}) \cup v y_{j},$ and $P_{7}^{2} = (C_{6}^{2} - v y_{j}) \cup v x_{i} .$

2. Base Constructions

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} ∖ E (K_{3})$ , $p \neq 1$ .

Proof. First we decompose $K_{7} ∖ E (K_{3})$ into 3 $C_{6}$ as follows:

${(x_{2} x_{5} x_{1} x_{4} x_{3} x_{6} x_{2}), (x_{2} x_{4} x_{6} x_{1} x_{3} x_{7} x_{2}), (x_{1} x_{2} x_{3} x_{5} x_{6} x_{7} x_{1})} .$

The bold edges (resp., ordinary edges) gives 2 $P_{7}$ from first two cycles. Now, the 3 $P_{7}$ are ${x_{4} x_{6} x_{7} x_{1} x_{2} x_{3} x_{5}, x_{7} x_{3} x_{6} x_{1} x_{4} x_{2} x_{5}, x_{7} x_{2} x_{6} x_{5} x_{1} x_{3} x_{4}} .$

Hence $K_{7} ∖ 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} x_{5} x_{8} x_{2} x_{6} x_{7} x_{1}), (x_{1} x_{3} x_{2} x_{7} x_{4} x_{8} x_{1})}, {(x_{5} x_{7} x_{3} x_{8} x_{6} x_{4} x_{5}), (x_{5} x_{2} x_{4} x_{1} x_{6} x_{3} x_{5})} .$

The last 3 $C_{6}$ can be decomposed into 3 $P_{7}$ as follows: ${x_{5} x_{8} x_{2} x_{6} x_{7} x_{1} x_{3}, x_{3} x_{2} x_{7} x_{5} x_{4} x_{8} x_{6}, x_{6} x_{4} x_{7} x_{3} x_{8} x_{1} x_{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} x_{3} x_{5} x_{7} x_{9} x_{2} x_{1}), (x_{1} x_{4} x_{6} x_{8} x_{2} x_{5} x_{1})}, {(x_{1} x_{6} x_{2} x_{3} x_{4} x_{7} x_{1}), \\ (x_{1} x_{8} x_{3} x_{7} x_{6} x_{9} x_{1})}, {(x_{4} x_{5} x_{6} x_{3} x_{9} x_{8} x_{4}), (x_{4} x_{2} x_{7} x_{8} x_{5} x_{9} x_{4})} . \end{aligned}$

The last 3 $C_{6}$ can be decomposed into 3 $P_{7}$ as follows: ${x_{1} x_{8} x_{3} x_{7} x_{6} x_{9} x_{5}, x_{5} x_{8} x_{7} x_{2} x_{4} x_{9} x_{3}, x_{3} x_{6} x_{5} x_{4} x_{8} x_{9} x_{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_{6 k, 4 l}$ , $k, l \in Z^{+}$ and $p \neq 1$ .

Proof. Let $V (K_{6, 4}) = {x_{1}, \dots, x_{6}} \cup {y_{1}, \dots, y_{4}}$ . First we decompose $K_{6, 4}$ into $C_{6}$ ’s as follows: ${(y_{2} x_{2} y_{3} x_{3} y_{1} x_{1} y_{2}), (y_{2} x_{5} y_{3} x_{6} y_{4} x_{4} y_{2})}, {(y_{1} x_{2} y_{4} x_{1} y_{3} x_{4} y_{1}), (y_{1} x_{5} y_{4} x_{3} y_{2} x_{6} y_{1})} .$

From the first 3 $C_{6}$ we can find 3 $P_{7}$ as follows: ${y_{1} x_{1} y_{3} x_{4} y_{2} x_{5} y_{3}, y_{3} x_{6} y_{4} x_{4} y_{1} x_{2} y_{4}, y_{4} x_{1} y_{2} x_{2} y_{3} x_{3} y_{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_{6 k, 4 l} = k l K_{6, 4}$ . Hence by Remark 1.3, $K_{6 k, 4 l}$ has a $(6; p, q)$ -decomposition.

Lemma 2.5. There exists a $(6; p, q)$ -decomposition of

(i). $K_{12 l + 1} ∖ E (2 l C_{6})$ with $p \neq 1$ and

(ii). $K_{12 k} ∖ E (2 k C_{6})$ with $p \geq 6 k$ , where $2 l C_{6}$ and $2 k C_{6}$ are vertex disjoint cycles and $k, l \in Z^{+}$ .

Proof. (i). Let $\begin{aligned} {{(x_{1} x_{4} x_{2} x_{6} x_{3} x_{5} x_{1}), (x_{1} x_{10} x_{4} x_{7} x_{2} x_{12} x_{1})}, {(x_{7} x_{13} x_{10} x_{12} x_{8} x_{11} x_{7}), (x_{7} x_{9} x_{12} x_{13} x_{8} x_{10} x_{7})}, \\ {(x_{8} x_{2} x_{10} x_{3} x_{7} x_{1} x_{8}), (x_{8} x_{5} x_{10} x_{6} x_{12} x_{4} x_{8})}, {(x_{9} x_{1} x_{3} x_{13} x_{11} x_{2} x_{9}), (x_{9} x_{4} x_{13} x_{5} x_{11} x_{6} x_{9})}, \\ {(x_{9} x_{11} x_{1} x_{13} x_{2} x_{5} x_{9}), (x_{9} x_{3} x_{11} x_{4} x_{6} x_{13} x_{9})}, (x_{3} x_{8} x_{6} x_{7} x_{5} x_{12} x_{3})}, \end{aligned}$ be the $C_{6}$ -decomposition of $K_{13} ∖ E (2 C_{6})$ , where 2 $C_{6}$ removed from $K_{13}$ are given by $(x_{1} x_{2} x_{3} x_{4} x_{5} x_{6} x_{1})$ ,
$(x_{7} x_{8} x_{9} x_{10} x_{11} x_{12} x_{7})$ . The last 3 $C_{6}$ can be decomposed into 3 $P_{7}$ as follows: ${x_{12} x_{3} x_{9} x_{13} x_{6} x_{4} x_{11}, x_{3} x_{8} x_{6} x_{7} x_{5} x_{9} x_{11}, x_{3} x_{11} x_{1} x_{13} x_{2} x_{5} x_{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} ∖ E (2 C_{6})$ has a $(6; p, q)$ -decomposition, where the $2 C_{6}$ removed from $K_{13}$ are vertex disjoint cycles. We can write $K_{12 l + 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_{12 l + 1} ∖ E (2 l C_{6})$ , where the $2 l C_{6}$ removed from $K_{12 l + 1}$ are vertex disjoint cycles.

(ii). Since the degree of each vertex $v \in V (K_{12 k} ∖ E (2 k C_{6}))$ is odd, then $p \geq 6 k$ . 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} x_{8} x_{3} x_{7} x_{2} x_{9} x_{1}), (x_{1} x_{7} x_{11} x_{5} x_{12} x_{4} x_{1})}, (x_{2} x_{5} x_{9} x_{6} x_{11} x_{8} x_{2})}, \end{aligned}$ be the ${6 P_{7}, 3 C_{6}}$ -decomposition of $K_{12} ∖ E (2 C_{6})$ , where the 2 $C_{6}$ removed from $K_{12}$ are
$(x_{1} x_{2} x_{3} x_{4} x_{5} x_{6} x_{1})$ , $(x_{7} x_{8} x_{9} x_{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_{6} x_{9} x_{5}, x_{5} x_{2} x_{8} x_{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} ∖ E (2 C_{6})$ has a $(6; p, q)$ -decomposition, where the $2 C_{6}$ removed from $K_{12}$ are vertex disjoint cycles. We can write $K_{12 k} = 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_{12 k} ∖ E (2 k C_{6})$ , where $2 k C_{6}$ removed from $K_{12 k}$ are vertex disjoint cycles.

Lemma 2.6. There exists a $(6; p, q)$ -decomposition of $K_{m} ∖ E (K_{3}), m \equiv 3, 7 (\mod 12)$ , $m > 3$ and $p \neq 1$ .

Proof. Let $m = 12 k + i$ , where $i = 3, 7$ . We prove it in two cases.

Case 1. $m = 12 k + 3$ . When $m = 15$ , $K_{15} ∖ E (K_{3}) = K_{9} \oplus (K_{7} ∖ E (K_{3})) \oplus K_{8, 6}$ . By Lemmas 2.1, 2.3 and 2.4 and Remark 1.3, $K_{15} ∖ E (K_{3})$ has a $(6; p, q)$ -decomposition. For $m > 15$ , we can write $K_{m} ∖ E (K_{3}) = K_{12 (k - 1) + 1}$ $\oplus (K_{15} ∖ E (K_{3})) \oplus K_{12 (k - 1), 14} = K_{12 (k - 1) + 1} \oplus (K_{15} ∖ 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} ∖ E (K_{3})$ has a $(6; p, q)$ -decomposition.

Case 2. $m = 12 k + 7$ . We can write $K_{m} ∖ E (K_{3}) = K_{12 k + 1} \oplus (K_{7} ∖ E (K_{3}))$ $\oplus K_{12 k, 6}$ . By Theorems 1.1, 1.2, Lemma 2.1 and Remark 1.3, $K_{m} ∖ E (K_{3})$ has a $(6; p, q)$ -decomposition.

Lemma 2.7. There exists a $(6; p, q)$ -decomposition of $K_{m} ∖ E (C_{4})$ for $m \equiv 5 (\mod 12)$ and $K_{m} ∖ E (C_{7})$ for $m \equiv 11 (\mod 12)$ .

Proof.

Case 1. $m \equiv 5 (\mod 12)$ . When $m = 17$ , $K_{17} ∖ E (C_{4}) = K_{8} \oplus K_{9} \oplus (K_{8, 9} ∖ E (C_{4}))$ . Let $V_{1} = V (K_{8}) = {x_{i} : 1 \leq i \leq 8}$ and $V_{2} = V (K_{9}) = {y_{i} : 1 \leq i \leq 9}$ . So, $V (K_{8, 9}) = V_{1} \cup V_{2}$ . Let $\begin{aligned} {(x_{1} y_{2} x_{2} y_{4} x_{3} y_{5} x_{1}), (x_{1} y_{1} x_{3} x_{4} y_{3} x_{2} x_{1})}, {(x_{5} y_{7} x_{2} y_{6} x_{4} y_{9} x_{5}), (x_{5} x_{6} y_{8} x_{7} x_{8} y_{6} x_{5})}, \\ {(x_{6} x_{8} x_{4} x_{1} x_{7} x_{2} x_{6}), (x_{6} x_{3} x_{1} x_{8} x_{5} x_{4} x_{6})}, {(y_{8} x_{2} y_{9} x_{6} y_{4} x_{1} y_{8}), (y_{8} x_{5} y_{1} x_{7} y_{6} x_{3} y_{8})}, \\ {(x_{8} y_{7} x_{6} y_{5} x_{2} y_{1} x_{8}), (x_{8} y_{8} x_{4} y_{7} x_{7} y_{9} x_{8})}, {(y_{3} x_{3} y_{2} x_{6} y_{6} x_{1} y_{3}), (y_{3} x_{7} y_{4} x_{4} y_{5} x_{5} y_{3})}, \\ {(x_{2} x_{5} x_{1} x_{6} x_{7} x_{3} x_{2}), (x_{4} x_{2} x_{8} x_{3} x_{5} x_{7} x_{4})}, {(x_{8} y_{5} x_{7} y_{2} x_{5} y_{4} x_{8}), (x_{8} y_{3} x_{6} y_{1} x_{4} y_{2} x_{8})}, \end{aligned}$ be the $C_{6}$ -decomposition of $K_{8} \oplus (K_{8, 9} ∖ E (C_{4}))$ . The first 3 $C_{6}$ can be decomposed into 3 $P_{7}$ as follows: ${x_{5} y_{7} x_{2} y_{6} x_{4} x_{3} y_{1}, y_{2} x_{2} y_{4} x_{3} y_{5} x_{1} y_{1}, x_{5} y_{9} x_{4} y_{3} x_{2} x_{1} y_{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} ∖ E (C_{4}))$ given above. Hence by Lemma 2.3 and Remark 1.3, $K_{17} ∖ E (C_{4})$ has a $(6; p, q)$ -decomposition. When $m > 17$ , we can write $K_{m} ∖ E (C_{4}) = K_{12 k + 5} ∖ E (C_{4}) = K_{12 (k - 1) + 1} \oplus (K_{17} ∖ 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} ∖ E (C_{4})$ has a $(6; p, q)$ -decomposition.

Case 2. $m \equiv 11 (\mod 12)$ . We can write $K_{m} ∖ E (C_{7}) = K_{12 l + 11} ∖ E (C_{7}) = K_{12 l + 1} \oplus K_{12 l, 10} \oplus (K_{11} ∖ E (C_{7}))$ and $K_{12 l, 10} = K_{12 l, 6} \oplus 2 l K_{6, 4}$ . Let $\begin{aligned} {(x_{1} x_{4} x_{10} x_{5} x_{7} x_{11} x_{1}), (x_{1} x_{8} x_{5} x_{11} x_{10} x_{3} x_{1})}, {(x_{2} x_{7} x_{3} x_{9} x_{6} x_{8} x_{2}), (x_{2} x_{11} x_{3} x_{5} x_{1} x_{10} x_{2})}, \\ {(x_{9} x_{4} x_{11} x_{6} x_{10} x_{7} x_{9}), (x_{9} x_{1} x_{6} x_{4} x_{8} x_{10} x_{9})}, {(x_{9} x_{8} x_{3} x_{6} x_{2} x_{5} x_{9}), (x_{9} x_{11} x_{8} x_{7} x_{4} x_{2} x_{9})}, \end{aligned}$ be the $C_{6}$ -decomposition of $K_{11} ∖ E (C_{7})$ . The first 3 $C_{6}$ can be decomposed into 3 $P_{7}$ as follows: ${(x_{1} x_{11} x_{4} x_{3} x_{7} x_{2} x_{8}, x_{8} x_{1} x_{4} x_{10} x_{5} x_{11} x_{7}, x_{1} x_{3} x_{9} x_{6} x_{8} x_{5} x_{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} ∖ E (C_{7})$ . By Theorems 1.1, 1.2, Lemma 2.4 and Remark 1.3, $K_{m} ∖ 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 (\mod 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 (\mod 12)$ . Let $m = 12 k$ 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} x_{8} x_{3} x_{7} x_{2} x_{9} x_{1}), (x_{1} x_{7} x_{11} x_{5} x_{12} x_{4} x_{1})}, {(x_{2} x_{5} x_{9} x_{6} x_{11} x_{8} x_{2}), \\ (x_{2} x_{3} x_{4} x_{5} x_{6} x_{1} x_{2})}, (x_{7} x_{8} x_{9} x_{10} x_{11} x_{12} x_{7})}, \end{aligned}$ be a ${6 P_{7}, 5 C_{6}}$ -decomposition of $K_{12}$ . For $p = 7$ , we decompose the last cycle and first path into $2 P_{7}$ as follows: ${x_{3} x_{9} x_{4} x_{8} x_{5} x_{7} x_{12}, x_{6} x_{7} x_{8} x_{9} x_{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_{12 k} = 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_{12 k}$ has a $(6; p, q)$ -decomposition.

Case 2. $m \equiv 4 (\mod 12)$ . Let $m = 12 k + 4$ and

$\begin{aligned} {x_{1} x_{5} x_{7} x_{4} x_{6} x_{8} x_{2}, x_{3} x_{6} x_{7} x_{2} x_{5} x_{8} x_{4}, x_{5} x_{3} x_{7} x_{8} x_{1} x_{2} x_{6}, x_{7} x_{1} x_{6} x_{5} x_{4} x_{3} x_{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} x_{9} x_{5} x_{11} x_{2} x_{10} x_{3}), (x_{3} x_{12} x_{5} x_{10} x_{4} x_{11} x_{3})}, \\ {(x_{9} x_{2} x_{12} x_{1} x_{15} x_{8} x_{9}), (x_{9} x_{4} x_{16} x_{6} x_{13} x_{7} x_{9})}, \\ {(x_{13} x_{3} x_{15} x_{5} x_{16} x_{2} x_{13}), (x_{13} x_{4} x_{15} x_{7} x_{11} x_{1} x_{13})}, \\ {(x_{8} x_{12} x_{7} x_{14} x_{5} x_{13} x_{8}), (x_{8} x_{11} x_{6} x_{9} x_{1} x_{10} x_{8})}, \\ {(x_{14} x_{6} x_{10} x_{7} x_{16} x_{8} x_{14}), (x_{14} x_{2} x_{15} x_{6} x_{12} x_{4} x_{14})}, \\ {(x_{1} x_{3} x_{14} x_{12} x_{10} x_{16} x_{1}), (x_{1} x_{14} x_{16} x_{3} x_{2} x_{4} x_{1})} \end{aligned}$ be a ${8 P_{7}, 12 C_{6}}$ -decomposition of $K_{16}$ .

For $p = 9$ , we decompose the last cycle and last path into $2 P_{7}$ as follows: ${x_{15} x_{14} x_{9} x_{13} x_{12} x_{16} x_{3}, x_{3} x_{2} x_{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_{12 k + 4} = K_{12 (k - 1)} \oplus K_{16} \oplus K_{12 (k - 1), 16}$ . By Lemma 2.4 and by applying Case 1, $K_{12 k + 4}$ has a $(6; p, q)$ -decomposition.

3. $(6; p, q)$ -decomposition of $K_{m} K_{n}$

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} K_{n}) = {x_{i, j} : 1 \leq i \leq m, 1 \leq j \leq n}$ .

Lemma 3.1. There exists a $(6; p, q)$ -decomposition of $K_{3} K_{3}$ , $p \neq 1$ .

Proof. First we decompose $K_{3} K_{3}$ into $C_{6}$ ’s as follows:
${(x_{1, 1} x_{1, 2} x_{3, 2} x_{3, 3} x_{2, 3} x_{1, 3} x_{1, 1}), (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 $3 P_{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} K_{3}$ has a $(6; p, q)$ -decomposition.

Lemma 3.2. There exists a $(6; p, q)$ -decomposition of $K_{3} K_{7}$ , $p \neq 1$ .

Proof. First we decompose $K_{3} K_{7}$ into $C_{6}$ ’s as follows:

${(x_{1, 6} 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} x_{1, 3} x_{1, 6})}$ ,
${(x_{1, 7} x_{3, 7} x_{3, 3} x_{3, 5} x_{2, 5} x_{1, 5} x_{1, 7}), (x_{1, 7} x_{2, 7} x_{3, 7} x_{3, 1} x_{3, 4} x_{1, 4} x_{1, 7})}$ ,
${(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} x_{1, 2} x_{1, 7})}$ ,
${(x_{2, 7} x_{2, 6} x_{2, 1} x_{2, 4} x_{2, 5} x_{2, 3} x_{2, 7}), (x_{2, 7} x_{2, 2} x_{2, 4} x_{2, 6} x_{2, 5} x_{2, 1} x_{2, 7})}$ ,
${(x_{3, 7} x_{3, 2} x_{3, 6} x_{3, 3} x_{3, 4} x_{3, 5} x_{3, 7}), (x_{3, 7} x_{3, 6} x_{3, 1} x_{3, 5} x_{3, 2} x_{3, 4} x_{3, 7})}$ ,
${(x_{1, 3} x_{3, 3} x_{3, 1} x_{2, 1} x_{2, 2} x_{1, 2} x_{1, 3}), (x_{1, 3} x_{2, 3} x_{3, 3} x_{3, 2} x_{1, 2} x_{1, 1} x_{1, 3})}$ ,
${(x_{2, 2} x_{2, 6} x_{2, 3} x_{2, 4} x_{2, 7} x_{2, 5} x_{2, 2}), (x_{2, 2} x_{3, 2} x_{3, 1} x_{1, 1} x_{2, 1} x_{2, 3} x_{2, 2})}$ .

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} K_{8}$ , $p \geq 12$ .

Proof. Since the degree of each vertex $v \in V (K_{3} 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}$ ,
${(x_{1, 2} x_{1, 5} x_{1, 4} x_{1, 8} x_{1, 1} x_{1, 6} x_{1, 2}), (x_{1, 2} x_{1, 3} x_{1, 7} x_{1, 4} x_{1, 6} x_{1, 8} x_{1, 2})}$ ,
${(x_{2, 6} x_{1, 6} x_{3, 6} x_{3, 2} x_{3, 5} x_{2, 5} x_{2, 6}), (x_{2, 6} x_{2, 2} x_{2, 5} x_{2, 4} x_{2, 8} x_{2, 1} x_{2, 6})}$ ,
${(x_{3, 3} 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} x_{3, 2} x_{3, 3})}$ .

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} K_{11}$ , $p \neq 1$ .

Proof. First we decompose $K_{3} K_{11}$ into $C_{6}$ ’s as follows: $\begin{aligned} {(x_{1, 2} x_{1, 1} x_{1, 8} x_{1, 3} x_{1, 9} x_{1, 10} x_{1, 2}), (x_{1, 2} x_{1, 4} x_{1, 6} x_{1, 1} x_{1, 7} x_{1, 9} x_{1, 2})}, \\ {(x_{1, 7} 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} x_{1, 8} x_{1, 7})}, \\ {(x_{1, 11} 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} x_{1, 6} x_{1, 11})}, \\ {(x_{2, 1} x_{2, 11} x_{2, 8} x_{2, 10} x_{2, 4} x_{2, 7} x_{2, 1}), (x_{2, 1} x_{2, 2} x_{2, 4} x_{2, 5} x_{2, 6} x_{2, 9} x_{2, 1})}, \\ {(x_{2, 6} x_{2, 3} x_{2, 5} x_{2, 9} x_{2, 7} x_{2, 2} x_{2, 6}), (x_{2, 6} x_{2, 10} x_{2, 9} x_{2, 2} x_{2, 5} x_{2, 1} x_{2, 6})}, \\ {(x_{2, 11} x_{2, 6} x_{2, 8} x_{2, 3} x_{2, 10} x_{2, 5} x_{2, 11}), (x_{2, 11} x_{2, 2} x_{2, 10} x_{2, 7} x_{2, 3} x_{2, 4} x_{2, 11})}, \\ {(x_{3, 1} x_{3, 11} x_{3, 8} x_{3, 7} x_{3, 9} x_{3, 4} x_{3, 1}), (x_{3, 1} x_{3, 3} x_{3, 10} x_{3, 11} x_{3, 6} x_{3, 9} x_{3, 1})}, \\ {(x_{3, 2} x_{3, 3} x_{3, 6} x_{3, 5} x_{3, 9} x_{3, 10} x_{3, 2}), (x_{3, 2} x_{3, 8} x_{3, 5} x_{3, 10} x_{3, 6} x_{3, 4} x_{3, 2})}, \\ {(x_{3, 1} 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} x_{3, 5} x_{3, 1})}, \\ {(x_{1, 1} x_{1, 3} x_{1, 4} x_{2, 4} x_{2, 1} x_{3, 1} x_{1, 1}), (x_{1, 1} x_{1, 5} x_{3, 5} x_{3, 3} x_{2, 3} x_{2, 1} x_{1, 1})}, \\ {(x_{2, 11} x_{3, 11} x_{3, 9} x_{1, 9} x_{2, 9} x_{2, 3} x_{2, 11}), (x_{2, 11} x_{1, 11} x_{1, 1} x_{1, 10} x_{3, 10} x_{2, 10} x_{2, 11})}, \\ {(x_{1, 5} x_{1, 7} x_{2, 7} x_{3, 7} x_{3, 4} x_{1, 4} x_{1, 5}), (x_{1, 5} x_{2, 5} x_{3, 5} x_{3, 11} x_{1, 11} x_{1, 2} x_{1, 5})}, \\ {(x_{1, 3} x_{1, 6} x_{2, 6} x_{2, 4} x_{3, 4} x_{3, 3} x_{1, 3}), (x_{1, 3} x_{1, 7} x_{3, 7} x_{3, 2} x_{2, 2} x_{2, 3} x_{1, 3})}, \\ {(x_{2, 8} x_{3, 8} x_{1, 8} x_{1, 10} x_{2, 10} x_{2, 1} x_{2, 8}), (x_{2, 8} x_{2, 4} x_{2, 9} x_{2, 11} x_{2, 7} x_{2, 5} x_{2, 8})}, \\ {(x_{3, 10} x_{3, 4} x_{3, 5} x_{3, 2} x_{3, 6} x_{3, 7} x_{3, 10}), (x_{3, 10} x_{3, 8} x_{3, 9} x_{3, 3} x_{3, 7} x_{3, 1} x_{3, 10})}, \\ {(x_{2, 8} x_{1, 8} x_{1, 6} x_{3, 6} x_{2, 6} x_{2, 7} x_{2, 8}), (x_{2, 8} x_{2, 9} x_{3, 9} x_{3, 2} x_{1, 2} x_{2, 2} x_{2, 8})}, \\ (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} K_{16}$ , $p \geq 24$ .

Proof. Since the degree of each vertex $v \in V (K_{3} 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} {(x_{1, 1} x_{1, 14} x_{1, 3} x_{1, 7} x_{1, 4} x_{1, 8} x_{1, 1}), (x_{1, 1} x_{1, 16} x_{1, 3} x_{1, 2} x_{1, 8} x_{1, 6} x_{1, 1})}, \\ {(x_{1, 3} x_{1, 9} x_{1, 5} x_{1, 11} x_{1, 2} x_{1, 10} x_{1, 3}), (x_{1, 3} x_{1, 12} x_{1, 5} x_{1, 10} x_{1, 4} x_{1, 11} x_{1, 3})}, \\ {(x_{1, 9} x_{1, 2} x_{1, 12} x_{1, 1} x_{1, 15} x_{1, 8} x_{1, 9}), (x_{1, 9} x_{1, 4} x_{1, 16} x_{1, 6} x_{1, 13} x_{1, 7} x_{1, 9})}, \\ {(x_{1, 8} x_{1, 12} x_{1, 7} x_{1, 14} x_{1, 5} x_{1, 13} x_{1, 8}), (x_{1, 8} x_{1, 11} x_{1, 6} x_{1, 9} x_{1, 1} x_{1, 10} x_{1, 8})}, \\ {(x_{1, 13} x_{1, 3} x_{1, 15} x_{1, 5} x_{1, 16} x_{1, 2} x_{1, 13}), (x_{1, 13} x_{1, 4} x_{1, 15} x_{1, 7} x_{1, 11} x_{1, 1} x_{1, 13})}, \\ {(x_{1, 14} x_{1, 6} x_{1, 10} x_{1, 7} x_{1, 16} x_{1, 8} x_{1, 14}), (x_{1, 14} x_{1, 2} x_{1, 15} x_{1, 6} x_{1, 12} x_{1, 4} x_{1, 14})}, \\ {(x_{2, 7} x_{2, 9} x_{2, 3} x_{2, 11} x_{2, 2} x_{2, 10} x_{2, 7}), (x_{2, 7} x_{2, 12} x_{2, 3} x_{2, 10} x_{2, 5} x_{2, 11} x_{2, 7})}, \\ {(x_{2, 9} x_{2, 2} x_{2, 12} x_{2, 4} x_{2, 15} x_{2, 8} x_{2, 9}), (x_{2, 9} x_{2, 5} x_{2, 16} x_{2, 6} x_{2, 13} x_{2, 1} x_{2, 9})}, \\ {(x_{2, 8} x_{2, 12} x_{2, 1} x_{2, 14} x_{2, 3} x_{2, 13} x_{2, 8}), (x_{2, 8} x_{2, 11} x_{2, 6} x_{2, 9} x_{2, 4} x_{2, 10} x_{2, 8})}, \\ {(x_{2, 13} x_{2, 7} x_{2, 15} x_{2, 3} x_{2, 16} x_{2, 2} x_{2, 13}), (x_{2, 13} x_{2, 5} x_{2, 15} x_{2, 1} x_{2, 11} x_{2, 4} x_{2, 13})}, \\ {(x_{2, 14} x_{2, 6} x_{2, 10} x_{2, 1} x_{2, 16} x_{2, 8} x_{2, 14}), (x_{2, 14} x_{2, 2} x_{2, 15} x_{2, 6} x_{2, 12} x_{2, 5} x_{2, 14})}, \\ {(x_{2, 4} x_{2, 14} x_{2, 7} x_{2, 6} x_{2, 3} x_{2, 8} x_{2, 4}), (x_{2, 4} x_{2, 16} x_{2, 7} x_{2, 1} x_{2, 8} x_{2, 5} x_{2, 4})}, \\ {(x_{3, 1} x_{3, 9} x_{3, 3} x_{3, 11} x_{3, 5} x_{3, 10} x_{3, 1}), (x_{3, 1} x_{3, 12} x_{3, 3} x_{3, 10} x_{3, 4} x_{3, 11} x_{3, 1})}, \\ {(x_{3, 9} x_{3, 5} x_{3, 12} x_{3, 2} x_{3, 15} x_{3, 8} x_{3, 9}), (x_{3, 9} x_{3, 4} x_{3, 16} x_{3, 6} x_{3, 13} x_{3, 7} x_{3, 9})}, \\ {(x_{3, 8} x_{3, 12} x_{3, 7} x_{3, 14} x_{3, 3} x_{3, 13} x_{3, 8}), (x_{3, 8} x_{3, 11} x_{3, 6} x_{3, 9} x_{3, 2} x_{3, 10} x_{3, 8})}, \\ {(x_{3, 13} x_{3, 1} x_{3, 15} x_{3, 3} x_{3, 16} x_{3, 5} x_{3, 13}), (x_{3, 13} x_{3, 4} x_{3, 15} x_{3, 7} x_{3, 11} x_{3, 2} x_{3, 13}}, \\ {(x_{3, 14} x_{3, 6} x_{3, 10} x_{3, 7} x_{3, 16} x_{3, 8} x_{3, 14}), (x_{3, 14} x_{3, 5} x_{3, 15} x_{3, 6} x_{3, 12} x_{3, 4} x_{3, 14}}, \\ {(x_{3, 2} x_{3, 14} x_{3, 1} x_{3, 5} x_{3, 8} x_{3, 3} x_{3, 2}), (x_{3, 2} x_{3, 16} x_{3, 1} x_{3, 7} x_{3, 6} x_{3, 8} x_{3, 2})}, \\ {(x_{1, 10} x_{1, 11} x_{1, 15} x_{1, 12} x_{1, 14} x_{1, 16} x_{1, 10}), (x_{1, 10} x_{1, 13} x_{1, 12} x_{1, 16} x_{1, 9} x_{1, 14} x_{1, 10})}, \\ {(x_{2, 14} x_{1, 14} x_{3, 14} x_{3, 10} x_{3, 13} x_{2, 13} x_{2, 14}), (x_{2, 14} x_{2, 10} x_{2, 13} x_{2, 12} x_{2, 16} x_{2, 9} x_{2, 14})}, \\ {(x_{3, 11} 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} x_{3, 10} x_{3, 11})}, \\ {(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})}, \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}, \\ 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}, \\ 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}, \\ 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}, \\ 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} K_{16}$ .

Lemma 3.6. There exists a $(6; p, q)$ -decomposition of $K_{6} K_{2}$ , $p \neq 1$ .

Proof. First we decompose $K_{6} K_{2}$ into $C_{6}$ ’s as follows:

${(x_{1, 2} x_{5, 2} x_{4, 2} x_{3, 2} x_{2, 2} x_{6, 2} x_{1, 2}), (x_{2, 1} x_{4, 1} x_{4, 2} x_{6, 2} x_{6, 1} x_{5, 1} x_{2, 1})}$ ,
${(x_{3, 2} x_{6, 2} x_{5, 2} x_{2, 2} x_{4, 2} x_{1, 2} x_{3, 2}), (x_{3, 2} x_{3, 1} x_{6, 1} x_{1, 1} x_{5, 1} x_{5, 2} x_{3, 2})}$ ,
${(x_{1, 1} x_{2, 1} x_{6, 1} x_{4, 1} x_{5, 1} x_{3, 1} x_{1, 1}), (x_{1, 1} x_{1, 2} x_{2, 2} x_{2, 1} x_{3, 1} x_{4, 1} x_{1, 1})}$ .

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} K_{4}$ , $p \neq 1$ .

Proof. First we decompose $K_{6} K_{4}$ into $C_{6}$ ’s as follows:

${(x_{3, 3} x_{1, 3} x_{2, 3} x_{2, 4} x_{3, 4} x_{3, 2} x_{3, 3}), (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} x_{1, 2} x_{2, 2} x_{2, 4} x_{1, 4} x_{1, 3}), (x_{1, 3} x_{6, 3} x_{3, 3} x_{3, 4} x_{5, 4} x_{5, 3} x_{1, 3})}$ ,
${(x_{4, 2} x_{3, 2} x_{5, 2} x_{6, 2} x_{6, 3} x_{4, 3} x_{4, 2}), (x_{4, 2} x_{4, 1} x_{3, 1} x_{6, 1} x_{6, 4} x_{6, 2} x_{4, 2})}$ ,
${(x_{1, 2} x_{3, 2} x_{2, 2} x_{2, 1} x_{1, 1} x_{1, 4} x_{1, 2}), (x_{1, 2} x_{1, 3} x_{4, 3} x_{2, 3} x_{2, 2} x_{4, 2} x_{1, 2})}$ ,
${(x_{6, 1} x_{6, 3} x_{2, 3} x_{5, 3} x_{4, 3} x_{4, 1} x_{6, 1}), (x_{6, 1} x_{1, 1} x_{5, 1} x_{5, 4} x_{2, 4} x_{2, 1} x_{6, 1})}$ ,
${(x_{3, 1} x_{1, 1} x_{4, 1} x_{2, 1} x_{2, 3} x_{3, 3} x_{3, 1}), (x_{3, 1} x_{5, 1} x_{5, 2} x_{1, 2} x_{6, 2} x_{3, 2} x_{3, 1})}$ ,
${(x_{1, 4} 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} x_{3, 4} x_{1, 4})}$ ,
${(x_{5, 1} x_{2, 1} x_{3, 1} x_{3, 4} x_{4, 4} x_{4, 1} x_{5, 1}), (x_{5, 1} x_{6, 1} x_{6, 2} x_{2, 2} x_{5, 2} x_{5, 3} x_{5, 1})}$ .

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} K_{6}$ , $p \neq 1$ .

Proof. First we decompose $K_{6} K_{6}$ into $C_{6}$ ’s as follows:

${(x_{1, 1} x_{1, 2} x_{2, 2} x_{3, 2} x_{6, 2} x_{6, 1} x_{1, 1}), (x_{1, 1} x_{3, 1} x_{4, 1} x_{5, 1} x_{6, 1} x_{2, 1} x_{1, 1})}$ ,
${(x_{2, 1} x_{2, 2} x_{4, 2} x_{4, 3} x_{4, 4} x_{4, 1} x_{2, 1}), (x_{2, 1} x_{3, 1} x_{6, 1} x_{4, 1} x_{1, 1} x_{5, 1} x_{2, 1})}$ ,
${(x_{1, 2} 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} x_{6, 2} x_{1, 2})}$
${(x_{1, 3} x_{5, 3} x_{5, 1} x_{5, 2} x_{6, 2} x_{6, 3} x_{1, 3}), (x_{1, 3} x_{1, 6} x_{1, 4} x_{6, 4} x_{6, 5} x_{1, 5} x_{1, 3})}$ ,
${(x_{1, 4} x_{1, 5} x_{3, 5} x_{2, 5} x_{5, 5} x_{5, 4} x_{1, 4}), (x_{1, 4} x_{4, 4} x_{5, 4} x_{2, 4} x_{6, 4} x_{3, 4} x_{1, 4})}$ ,
${(x_{1, 5} x_{5, 5} x_{5, 1} x_{5, 6} x_{5, 2} x_{1, 2} x_{1, 5}), (x_{1, 5} x_{4, 5} x_{4, 2} x_{1, 2} x_{1, 6} x_{1, 1} x_{1, 5})}$
${(x_{1, 6} 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} x_{1, 5} x_{1, 6})}$ ,
${(x_{3, 3} x_{2, 3} x_{6, 3} x_{5, 3} x_{5, 4} x_{3, 4} x_{3, 3}), (x_{3, 3} x_{4, 3} x_{4, 5} x_{6, 5} x_{5, 5} x_{5, 3} x_{3, 3})}$ ,
${(x_{5, 6} x_{4, 6} x_{4, 4} x_{2, 4} x_{2, 6} x_{3, 6} x_{5, 6}), (x_{5, 6} x_{6, 6} x_{6, 4} x_{4, 4} x_{4, 5} x_{5, 5} x_{5, 6})}$
${(x_{3, 4} x_{3, 5} x_{4, 5} x_{4, 6} x_{4, 2} x_{4, 4} x_{3, 4}), (x_{3, 4} x_{2, 4} x_{2, 3} x_{2, 6} x_{1, 6} x_{3, 6} x_{3, 4})}$ ,
${(x_{6, 3} x_{6, 4} x_{5, 4} x_{5, 6} x_{5, 3} x_{4, 3} x_{6, 3}), (x_{6, 3} x_{3, 3} x_{3, 5} x_{6, 5} x_{6, 1} x_{6, 6} x_{6, 3})}$ ,
${(x_{2, 3} x_{2, 5} x_{4, 5} x_{4, 1} x_{4, 6} x_{4, 3} x_{2, 3}), (x_{2, 3} x_{2, 2} x_{2, 5} x_{2, 4} x_{1, 4} x_{1, 3} x_{2, 3})}$ ,
${(x_{3, 1} x_{3, 6} x_{3, 2} x_{5, 2} x_{5, 5} x_{3, 5} x_{3, 1}), (x_{3, 1} x_{3, 4} x_{3, 2} x_{3, 5} x_{3, 6} x_{3, 3} x_{3, 1})}$ ,
${(x_{6, 2} 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} x_{2, 2} x_{6, 2})}$ ,
${(x_{5, 2} x_{5, 4} x_{5, 1} x_{3, 1} x_{3, 2} x_{4, 2} x_{5, 2}), (x_{5, 2} x_{5, 3} x_{2, 3} x_{2, 1} x_{2, 4} x_{2, 2} x_{5, 2})}$ .

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} K_{8}$ , $p \neq 1$ .

Proof. By Lemma 2.2, $K_{8} - I$ has a $(6; p, q)$ -decomposition. We decompose $8 K_{6} \oplus 6 I$ into $C_{6}$ ’s as follows: $\begin{aligned} {(x_{3, j} x_{2, j} x_{6, j} x_{4, j} x_{5, j} x_{1, j} x_{3, j}), (x_{3, j} x_{5, j} x_{5, j + 1} x_{1, j + 1} x_{1, j} x_{6, j} x_{3, j})}, \\ {(x_{3, j + 1} x_{2, j + 1} x_{2, j} x_{1, j} x_{4, j} x_{3, j} x_{3, j + 1}), (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})}, \\ {(x_{4, j + 1} x_{1, j + 1} x_{6, j + 1} x_{3, j + 1} x_{5, j + 1} x_{2, j + 1} x_{4, j + 1}),, (x_{4, j + 1} x_{4, j} x_{2, j} x_{5, j} x_{6, j} x_{6, j + 1} x_{4, j + 1})}, \end{aligned}$ where $j = 1, 3, \dots, 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} K_{4}$ , $p \neq 1$ .

Proof. First we decompose $K_{4} K_{4}$ into $C_{6}$ ’s as follows:

${(x_{2, 1} x_{4, 1} x_{1, 1} x_{1, 2} x_{2, 2} x_{2, 3} x_{2, 1}), (x_{2, 1} x_{3, 1} x_{3, 4} x_{3, 2} x_{2, 2} x_{2, 4} x_{2, 1})}$ ,
${(x_{2, 3} x_{1, 3} x_{1, 4} x_{3, 4} x_{4, 4} x_{2, 4} x_{2, 3}), (x_{2, 3} x_{3, 3} x_{3, 1} x_{3, 2} x_{4, 2} x_{4, 3} x_{2, 3})}$ ,
${(x_{1, 1} 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} x_{3, 1} x_{1, 1})}$ ,
${(x_{4, 4} x_{1, 4} x_{2, 4} x_{3, 4} x_{3, 3} x_{4, 3} x_{4, 4}), (x_{4, 4} x_{4, 2} x_{1, 2} x_{1, 3} x_{4, 3} x_{4, 1} x_{4, 4})}$ .

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_{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} K_{7}$ , $p \neq 1$ .

Proof. We can write $K_{7} K_{7} = 7 K_{7} ∖ E (K_{3}) \oplus K_{3} \oplus 7 K_{7} ∖ E (K_{3}) \oplus K_{3}$ . By Lemma 2.1, $K_{7} ∖ E (K_{3})$ has a $(6; p, q)$ -decomposition. Now, we can view $7 K_{3} \oplus 7 K_{3}$ as $K_{3}^{1} \oplus \dots \oplus K_{3}^{7} \oplus (K_{3}^{1})^{'} \oplus \dots \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, \dots, 7$ and $(K_{3}^{i})^{'} = (x_{i, i} x_{i + 1, i} x_{i + 2, i} x_{i, i})$ , for $i = 1, \dots, 7$ , where the subscripts of $x$ are taken modulo 7 with residues ${1, \dots, 7}$ . The $C_{6}$ -decomposition of $7 K_{3} \oplus 7 K_{3}$ is given below: $\begin{aligned} {(x_{3, 1} x_{1, 1} x_{2, 1} x_{2, 7} x_{2, 2} x_{3, 2} x_{3, 1}), (x_{3, 1} x_{3, 3} x_{3, 2} x_{4, 2} x_{2, 2} x_{2, 1} x_{3, 1})}, \\ {(x_{4, 4} x_{4, 2} x_{4, 3} x_{3, 3} x_{5, 3} x_{5, 4} x_{4, 4}), (x_{4, 4} x_{6, 4} x_{5, 4} x_{5, 5} x_{5, 3} x_{4, 3} x_{4, 4})}, \\ {(x_{7, 7} x_{1, 7} x_{1, 6} x_{6, 6} x_{6, 5} x_{7, 5} x_{7, 7}), (x_{7, 7} x_{2, 7} x_{1, 7} x_{1, 1} x_{1, 6} x_{7, 6} x_{7, 7})}, \\ (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} K_{12}$ , $p \geq 18$ .

Proof. Since the degree of each vertex $v \in V (K_{3} K_{12})$ is odd, then $p \geq \frac{36}{2} = 18$ . We can write $K_{3} K_{12} = 12 K_{3} \oplus 3 K_{12} = 12 K_{3} \oplus 3 ((K_{12} ∖ E (2 C_{6}))$ $\oplus 2 C_{6})$ . The graph $12 K_{3}$ along with three rows of $2 C_{6}$ can be viewed as $2 G$ , where $G = 6 K_{3} \oplus C_{6}^{1} \oplus C_{6}^{2} \oplus C_{6}^{3}$ with $V (G) = {x_{i, j} : 1 \leq i \leq 3, 1 \leq j \leq 6}$ 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:

${(x_{1, 1} x_{1, 2} x_{1, 5} x_{2, 5} x_{2, 3} x_{1, 3} x_{1, 1}), (x_{1, 1} x_{2, 1} x_{2, 2} x_{1, 2} x_{3, 2} x_{3, 1} x_{1, 1})}$ ,
${(x_{1, 6} x_{1, 4} x_{2, 4} x_{2, 2} x_{3, 2} x_{3, 6} x_{1, 6}), (x_{1, 6} x_{2, 6} x_{3, 6} x_{3, 4} x_{3, 3} x_{1, 3} x_{1, 6})}$ ,
${(x_{3, 5} x_{2, 5} x_{2, 4} x_{3, 4} x_{1, 4} x_{1, 5} x_{3, 5}), (x_{3, 5} x_{3, 1} x_{2, 1} x_{2, 6} x_{2, 3} x_{3, 3} x_{3, 5})}$ .

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} K_{12}$ , $p \geq 30$ .

Proof. Since the degree of each vertex $v \in V (K_{5} K_{12})$ is odd, then $p \geq 30$ . We can write $K_{5} K_{12}$ $= 12 K_{5} \oplus 5 K_{12} = 12 K_{5} \oplus 5 ((K_{12} ∖ E (2 C_{6})) \oplus 2 C_{6})$ . By Lemma 2.5, $K_{12} ∖ E (2 C_{6})$ has a $(6; p, q)$ -decomposition. Let $12 K_{5} \oplus 10 C_{6} = G_{1} \oplus G_{2}$ , where $G_{1} = (6 K_{5} \oplus C_{6}^{1} \oplus \dots \oplus C_{6}^{5}) ≅ 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} {(x_{1, 2} x_{1, 4} x_{5, 4} x_{4, 4} x_{4, 2} x_{3, 2} x_{1, 2}), (x_{1, 2} x_{2, 2} x_{2, 4} x_{3, 4} x_{5, 4} x_{5, 2} x_{1, 2})}, \\ {(x_{1, 6} 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} x_{1, 5} x_{1, 6})}, \\ {(x_{1, 3} x_{2, 3} x_{2, 6} x_{5, 6} x_{4, 6} x_{4, 3} x_{1, 3}), (x_{1, 3} x_{1, 5} x_{5, 5} x_{3, 5} x_{3, 3} x_{5, 3} x_{1, 3})}, \\ {(x_{2, 1} x_{2, 5} x_{3, 5} x_{4, 5} x_{4, 1} x_{1, 1} x_{2, 1}), (x_{2, 1} x_{2, 4} x_{1, 4} x_{3, 4} x_{3, 1} x_{4, 1} x_{2, 1})}, \\ {(x_{4, 2} x_{5, 2} x_{5, 1} x_{3, 1} x_{1, 1} x_{1, 2} x_{4, 2}), (x_{4, 2} x_{2, 2} x_{3, 2} x_{3, 5} x_{1, 5} x_{4, 5} x_{4, 2})}, \\ {(x_{4, 6} x_{3, 6} x_{3, 2} x_{5, 2} x_{2, 2} x_{2, 6} x_{4, 6}), (x_{4, 6} x_{1, 6} x_{5, 6} x_{5, 4} x_{2, 4} x_{4, 4} x_{4, 6})}, \\ {(x_{3, 3} x_{4, 3} x_{4, 1} x_{5, 1} x_{1, 1} x_{1, 3} x_{3, 3}), (x_{3, 3} x_{2, 3} x_{5, 3} x_{5, 1} x_{2, 1} x_{3, 1} x_{3, 3})}, \\ (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} K_{12}$ , $p \geq 42$ .

Proof. Since the degree of each vertex $v \in V (K_{7} K_{12})$ is odd, then $p \geq 42$ . We can write $K_{7} K_{12} = 12 K_{7} \oplus 7 K_{12} = 12 (K_{7} ∖ E (K_{3})) \oplus 4 K_{12} \oplus (K_{3} 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} K_{12}$ , $p \geq 66$ .

Proof. Since the degree of each vertex $v \in V (K_{11} K_{12})$ is odd, then $p \geq 66$ . We can write $K_{11} K_{12} = 12 K_{11} \oplus 11 K_{12} = 12 (K_{11} ∖ E (C_{7})) \oplus 11 K_{12}$ . Consider $K_{12}$ in rows 1, 3, 4, 7 as $(K_{12} ∖ E (2 C_{6})) \oplus 2 C_{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 = (4 C_{6} \oplus 6 C_{7}) \oplus (4 C_{6} \oplus 6 C_{7}) = G_{1} \oplus G_{2}$ , $G_{1} ≅ G_{2}$ . Let $G_{1} = C_{6}^{1} \oplus \dots \oplus C_{6}^{4} \oplus C_{7}^{1} \oplus \dots \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} {(x_{1, 2} x_{3, 2} x_{3, 1} x_{5, 1} x_{6, 1} x_{1, 1} x_{1, 2}), (x_{1, 2} x_{1, 5} x_{2, 5} x_{4, 5} x_{4, 2} x_{2, 2} x_{1, 2})}, \\ {(x_{7, 2} x_{7, 1} x_{4, 1} x_{4, 2} x_{5, 2} x_{6, 2} x_{7, 2}), (x_{7, 2} x_{3, 2} x_{3, 3} x_{5, 3} x_{6, 3} x_{7, 3} x_{7, 2})}, \\ {(x_{7, 4} x_{7, 3} x_{4, 3} x_{4, 4} x_{5, 4} x_{6, 4} x_{7, 4}), (x_{7, 4} x_{3, 4} x_{3, 5} x_{5, 5} x_{6, 5} x_{7, 5} x_{7, 4})}, \\ {(x_{7, 6} x_{7, 5} x_{4, 5} x_{4, 6} x_{5, 6} x_{6, 6} x_{7, 6}), (x_{7, 6} x_{7, 1} x_{3, 1} x_{3, 5} x_{1, 5} x_{1, 6} x_{7, 6})}, \\ {(x_{1, 3} x_{1, 4} x_{2, 4} x_{3, 4} x_{3, 6} x_{3, 3} x_{1, 3}), (x_{1, 3} x_{2, 3} x_{4, 3} x_{4, 1} x_{2, 1} x_{1, 1} x_{1, 3})}, \\ (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} ∖ E (C_{7})$ and $K_{12} ∖ E (C_{6})$ have a $(6; p, q)$ -decomposition. Hence by Remark 1.3, $K_{11} K_{12}$ has a $(6; p, q)$ -decomposition.

Lemma 3.16. There exists a $(6; p, q)$ -decomposition of $C_{6} (K_{8} ∖ E (2 C_{6}))$ , where $p = 24$ and the $2 C_{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} (K_{8} ∖ E (2 C_{6}))) = {x_{i, j} : 1 \leq i \leq 6, 1 \leq j \leq 8}$ . Since the degree of each vertex $v \in V (G)$ is odd and $| E (G) | = 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, \dots, 6}}$ .

Lemma 3.17. There exists a $(6; p, q)$ -decomposition of $K_{8} K_{9}$ , $p \geq 36$ .

Proof. Since the degree of each vertex $v \in V (K_{8} 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

${(x_{1, 7} x_{1, 2} x_{1, 6} x_{1, 5} x_{1, 1} x_{1, 8} x_{1, 7}), (x_{1, 7} x_{1, 4} x_{1, 5} x_{1, 3} x_{1, 6} x_{1, 1} x_{1, 7})}$ ,
${(x_{1, 7} x_{3, 7} x_{6, 7} x_{4, 7} x_{2, 7} x_{8, 7} x_{1, 7}), (x_{1, 7} x_{1, 6} x_{1, 9} x_{1, 4} x_{1, 2} x_{1, 5} x_{1, 7})}$ ,
${(x_{1, 3} x_{1, 4} x_{1, 6} x_{1, 8} x_{1, 5} x_{1, 9} x_{1, 3}), (x_{1, 3} x_{6, 3} x_{8, 3} x_{5, 3} x_{3, 3} x_{7, 3} x_{1, 3})}$ ,
${(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} x_{2, 6} x_{2, 1})}$ ,
${(x_{2, 1} 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} x_{2, 5} x_{2, 1})}$ ,
${(x_{3, 2} x_{3, 8} x_{3, 3} x_{3, 7} x_{3, 9} x_{3, 1} x_{3, 2}), (x_{3, 2} x_{3, 5} x_{3, 7} x_{3, 6} x_{3, 9} x_{3, 4} x_{3, 2})}$ ,
${(x_{3, 4} x_{3, 8} x_{3, 9} x_{3, 2} x_{3, 3} x_{3, 1} x_{3, 4}), (x_{3, 4} x_{3, 6} x_{3, 8} x_{3, 5} x_{3, 9} x_{3, 3} x_{3, 4})}$ ,
${(x_{4, 4} x_{4, 6} x_{4, 8} x_{4, 5} x_{4, 9} x_{4, 3} x_{4, 4}), (x_{4, 4} x_{4, 5} x_{4, 3} x_{4, 6} x_{4, 1} x_{4, 7} x_{4, 4})}$ ,
${(x_{4, 9} x_{4, 2} x_{4, 3} x_{4, 1} x_{4, 4} x_{4, 8} x_{4, 9}), (x_{4, 9} x_{5, 9} x_{7, 9} x_{2, 9} x_{3, 9} x_{8, 9} x_{4, 9})}$ ,
${(x_{4, 8} x_{4, 7} x_{4, 2} x_{4, 6} x_{4, 5} x_{4, 1} x_{4, 8}), (x_{4, 8} x_{2, 8} x_{8, 8} x_{1, 8} x_{3, 8} x_{6, 8} x_{4, 8})}$ ,
${(x_{5, 2} x_{5, 8} x_{5, 3} x_{5, 7} x_{5, 9} x_{5, 1} x_{5, 2}), (x_{5, 2} x_{5, 5} x_{5, 7} x_{5, 6} x_{5, 9} x_{5, 4} x_{5, 2})}$ ,
${(x_{5, 5} x_{5, 1} x_{5, 8} x_{5, 7} x_{5, 2} x_{5, 6} x_{5, 5}), (x_{5, 5} x_{5, 3} x_{5, 6} x_{5, 1} x_{5, 7} x_{5, 4} x_{5, 5})}$ ,
${(x_{6, 2} x_{6, 8} x_{6, 3} x_{6, 7} x_{6, 9} x_{6, 1} x_{6, 2}), (x_{6, 2} x_{6, 6} x_{6, 5} x_{6, 1} x_{6, 8} x_{6, 7} x_{6, 2})}$ ,
${(x_{6, 4} 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} x_{6, 1} x_{6, 4})}$ ,
${(x_{7, 2} x_{7, 8} x_{7, 3} x_{7, 7} x_{7, 9} x_{7, 1} x_{7, 2}), (x_{7, 2} x_{7, 5} x_{7, 7} x_{7, 6} x_{7, 9} x_{7, 4} x_{7, 2})}$ ,
${(x_{7, 7} x_{7, 1} x_{7, 4} x_{7, 8} x_{7, 9} x_{7, 2} x_{7, 7}), (x_{7, 7} x_{7, 4} x_{7, 5} x_{7, 3} x_{7, 1} x_{7, 8} x_{7, 7})}$ ,
${(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} x_{8, 2} x_{8, 6})}$ ,
${(x_{8, 3} x_{8, 1} x_{8, 4} x_{8, 8} x_{8, 9} x_{8, 2} x_{8, 3}), (x_{8, 3} x_{8, 6} x_{8, 1} x_{8, 7} x_{8, 4} x_{8, 5} x_{8, 3})}$ ,
${(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} x_{7, 1} x_{2, 1} x_{3, 1})}$ ,
${(x_{7, 2} x_{6, 2} x_{2, 2} x_{5, 2} x_{1, 2} x_{4, 2} x_{7, 2}), (x_{7, 2} x_{2, 2} x_{3, 2} x_{8, 2} x_{4, 2} x_{5, 2} x_{7, 2})}$ ,
${(x_{2, 3} x_{5, 3} x_{1, 3} x_{4, 3} x_{7, 3} x_{6, 3} x_{2, 3}), (x_{2, 3} x_{3, 3} x_{8, 3} x_{4, 3} x_{5, 3} x_{7, 3} x_{2, 3})}$ ,
${(x_{1, 4} x_{6, 4} x_{8, 4} x_{5, 4} x_{3, 4} x_{7, 4} x_{1, 4}), (x_{1, 4} x_{3, 4} x_{6, 4} x_{4, 4} x_{2, 4} x_{8, 4} x_{1, 4})}$ ,
${(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} x_{5, 5} x_{7, 5} x_{2, 5})}$ ,
${(x_{1, 6} x_{4, 6} x_{7, 6} x_{6, 6} x_{2, 6} x_{5, 6} x_{1, 6}), (x_{2, 6} x_{3, 6} x_{8, 6} x_{4, 6} x_{5, 6} x_{7, 6} x_{2, 6})}$ ,
${(x_{5, 7} x_{1, 7} x_{4, 7} x_{7, 7} x_{6, 7} x_{2, 7} x_{5, 7}), (x_{5, 7} x_{3, 7} x_{7, 7} x_{1, 7} x_{6, 7} x_{8, 7} x_{5, 7})}$ ,
${(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} x_{7, 8} x_{1, 8})}$ ,
${(x_{1, 9} 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} x_{5, 9} x_{1, 9})}$ .

For $p = 37$ , we decompose the last path and first cycle into $2 P_{7}$ as follows: ${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}} .$

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} K_{9}$ .

Theorem 3.18. $K_{m} K_{n}$ has a $(6; p, q)$ -decomposition if and only if $m n (m + n - 2) \equiv 0 (\mod 12)$ .

Proof. Necessity. Since $K_{m} K_{n}$ is $(m + n - 2)$ -regular with $m n$ vertices, $K_{m} K_{n}$ has $m n (m + n - 2) / 2$ edges. Now, assume that $K_{m} K_{n}$ has a $(6; p, q)$ -decomposition. Then the number of edges in the graph must be divisible by 6, i.e., $12 | m n (m + n - 2)$ and hence $m n (m + n - 2) \equiv 0 (\mod 12)$ .
Sufficiency. We construct the required decomposition in ten cases.

Case 1. $m \equiv 0 (\mod 6)$ and $n \equiv 0 (\mod 2)$ .

Subcase 1.1. $m, n \equiv 0 (\mod 6)$ .

Let $m = 6 k$ and $n = 6 l$ , where $k, l > 0$ are integers. We can write $K_{m} K_{n} = k l (K_{6} K_{6}) \oplus 3 k l (k + l - 2) K_{6, 6}$ . By Theorem 1.2 and Lemma 3.8, $K_{6, 6}$ and $K_{6} K_{6}$ have a $(6; p, q)$ -decomposition. Hence by Remark 1.3, $K_{m} K_{n}$ has a $(6; p, q)$ -decomposition.

Subcase 1.2. $m \equiv 0 (\mod 6), n \equiv 4 (\mod 6)$ .

Let $m = 6 k$ and $n = 6 l + 4$ , where $k, l$ are non-negative integers. We can write $K_{m} K_{n} = (K_{6 k} K_{6 l}) \oplus k (K_{6} K_{4}) \oplus 2 k (k - 1) K_{6, 6} \oplus 6 k K_{6 l, 4}$ . By Theorem 12, Lemmas 3.7, and 2.4, Subcase 1.1 and Remark 1.3, $K_{m} K_{n}$ has a $(6; p, q)$ -decomposition.

Subcase 1.3. $m \equiv 0 (\mod 6), n \equiv 2 (\mod 6)$ .

When $m = 6 k$ and $n = 2$ , $K_{m} K_{n} = k (K_{6} K_{2}) \oplus k (k - 1) K_{6, 6}$ . By Theorem 1.2, Lemma 3.6 and Remark 1.3, $K_{m} K_{n}$ has a $(6; p, q)$ -decomposition. When $m = 6 k$ and $n = 8$ , $K_{m} K_{n} = k (K_{6} K_{8}) \oplus 4 k (k - 1) K_{6, 6}$ . By Theorem 1.2, Lemma 3.9 and Remark 1.3, $K_{m} K_{n}$ has a $(6; p, q)$ -decomposition. When $n > 8$ , let $m = 6 k, n = 6 l + 8$ , where $k, l$ are non-negative integers. We can write $K_{m} K_{n} = (K_{6 k} K_{6 l}) \oplus (K_{6 k} K_{8}) \oplus 6 k K_{6 l, 8}$ . By Theorem 1.2, Lemma 2.4, Subcase 1.1 and Remark 1.3, $K_{m} K_{n}$ has a $(6; p, q)$ -decomposition.

Case 2. $m, n \equiv 4 (\mod 6)$ .

Let $m = 6 k + 4$ and $n = 6 l + 4$ , where $k, l$ are non-negative integers. We can write $K_{m} K_{n} = k l (K_{6} K_{6}) \oplus (k + l) (K_{6} K_{4}) \oplus (K_{4} K_{4}) \oplus (3 k l (k + l - 2) + 2 k (k - 1)) K_{6, 6} \oplus (12 k l + 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} K_{n}$ has a $(6; p, q)$ -decomposition.

Case 3. $m \equiv 0, 1, 4 o r 9 (\mod 12)$ , $n \equiv 1 o r 9 (\mod 12)$ .

When $m$ is even, the degree of each vertex $v \in V (K_{m} K_{n})$ is odd, then $p \geq m n / 2$ . Now, $K_{m} K_{n} = n K_{m} \oplus m K_{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} K_{n}$ has the required decomposition.

Case 4. $m, n \equiv 3 o r 7 (\mod 12)$ .

Subcase 4.1. $m, n \equiv i (\mod 12)$ , $i = 3, 7$ .

When $m = n$ , if $i = 3$ , then $K_{m} K_{n} = n K_{m} \oplus m K_{n} = 2 m (K_{m} ∖ E (K_{3})) \oplus \frac{m}{3} (K_{3} K_{3})$ . If $i = 7$ let $m = 12 k + 7$ , then $K_{m} K_{n} = 2 (m - 7) (K_{m} ∖ E (K_{3})) \oplus \frac{(m - 7)}{3} (K_{3} K_{3}) \oplus 14 (K_{12 k + 1} \oplus K_{12 k, 6}) \oplus K_{7} K_{7}$ . By Lemmas 2.6,3.1, 3.11, Theorems 1.1, 1.2 and Remark 1.3, $K_{m} K_{n}$ has a $(6; p, q)$ -decomposition.

When $m < n$ , let $n = m + h$ , where $h = 12 l, l \in Z^{+} m = 12 k + i$ , $i = 3, 7$ . We can write $K_{m} K_{n} = (K_{m} K_{m}) \oplus h K_{m} \oplus m (K_{n} ∖ E (K_{m})) = (K_{m} K_{m}) \oplus 12 l (K_{m} ∖ E (K_{3})) \oplus 12 l K_{3} \oplus m (K_{12 l + 1} \oplus K_{12 l, m - 1})$ . Now, the first three rows of $(K_{m} K_{n}) ∖ (K_{m} K_{m})$ can be viewed as $(K_{12 l + 1} ∖ E (2 l C_{6})) \oplus K_{12 l, m - 1} \oplus 2 l C_{6}$ . As in the proof of Lemma 3.12, we can prove $12 l K_{3}$ along with three rows of $2 l C_{6}$ has a $(6; p, q)$ -decomposition. By Lemmas 2.4 and 2.5 and Theorem 1.2, $K_{12 l + 1} ∖ E (2 l C_{6})$ and $K_{12 l, m - 1}$ have a $(6; p, q)$ -decomposition. Hence by Remark 1.3, $K_{m} K_{n}$ has a $(6; p, q)$ -decomposition.

Subcase 4.2. $m \equiv 3 (\mod 12), n \equiv 7 (\mod 12)$ .

Let $m = 12 k + 3, n = 12 l + 7$ . We can write $K_{m} K_{n} = n K_{m} \oplus m K_{n}$ .

When $k = l$ , every column of $K_{m} K_{n}$ can be viewed as $(K_{m} ∖ E (K_{3})) \oplus K_{3}$ and every first $(m - 3)$ rows can be viewed as $(K_{n} ∖ E (K_{3})) \oplus K_{3}$ and last three rows can be viewed as $(K_{n} ∖ 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} K_{3})$ and $K_{n} ∖ E (K_{7})$ can be viewed as $K_{12 l + 1} \oplus K_{12 l, 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} ∖ E (K_{3}), K_{n} ∖ E (K_{3})$ and $(K_{3} K_{3})$ have a $(6; p, q)$ -decomposition. By Lemma 3.2, the remaining graph $K_{3} K_{7}$ has a $(6; p, q)$ -decomposition.

When $k < l$ , every column of $K_{m} K_{n}$ can be viewed as $(K_{m} ∖ E (K_{3})) \oplus K_{3}$ and every first $(m - 3)$ rows can be viewed as $(K_{n} ∖ 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} K_{3})$ . By Lemmas 2.6 and 3.1, $K_{m} ∖ E (K_{3}), K_{n} ∖ E (K_{3})$ and $(K_{3} 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} K_{n}$ . Now, every $12 (l - k) + 7$ columns of $K_{m} K_{n}$ can be viewed as $(K_{m} ∖ E (K_{3})) \oplus (K_{m} ∖ V (K_{m - 3}))$ and every last three rows of $K_{m} K_{n}$ can be viewed as $K_{12 k + 1} \oplus K_{7} \oplus K_{12 k, 6} \oplus K_{12 (l - k), 6} \oplus K_{12 k, 12 (l - k)} \oplus (K_{12 (l - k) + 1} ∖ E (2 (l - k) C_{6})) \oplus 2 (l - k) C_{6}$ and by Theorem 1.2, $K_{12 k, 6} \oplus K_{12 (l - k), 6} = K_{12 l, 6}$ has a $(6; p, q)$ -decomposition. By Lemma 2.5, $K_{12 (l - k) + 1} ∖ 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} ∖ 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} K_{7}$ has a $(6; p, q)$ -decomposition.

By using similar proof, we can prove for the case $k > l$ also. Hence $K_{m} K_{n}$ has a $(6; p, q)$ -decomposition.

Case 5. $m \equiv 3 (\mod 12), n \equiv 11 (\mod 12)$ .

Let $m = 12 k + 3, n = 12 l + 11$ . We can write $K_{m} K_{n} = n K_{m} \oplus m K_{n}$ . Consider all columns as $(K_{m} ∖ E (K_{3})) \oplus K_{3}$ except the columns 1, 3, 4 and 7 and consider these columns as $(K_{m} ∖ (E (K_{3})) \oplus E (2 k C_{6})) \oplus K_{3} \oplus 2 k C_{6}$ and all rows can be viewed as $(K_{n} ∖ E (C_{7})) \oplus C_{7}$ except the last three rows. The last three rows can be viewed as $(K_{12 l + 1} ∖ E (2 l C_{6})) \oplus K_{12 l, 10} \oplus 2 l C_{6} \oplus K_{11}$ . In each column $K_{m} ∖ E (K_{3})$ has a $(6; p, q)$ -decomposition and in columns 1, 3, 4 and 7 the graph $(K_{m} ∖ (E (K_{3})) \oplus E (2 k C_{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 2 k C_{6}$ and in other columns form $K_{3}$ . By Lemma 2.7 and Theorem 1.1, the graphs $K_{n} ∖ E (C_{7})$ and $K_{12 l + 1}$ have a $(6; p, q)$ -decomposition and $K_{12 l, 10} = 2 l (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 $12 k C_{7}$ and in the last three rows form $K_{11} \oplus 2 l C_{6}$ . The graph $12 l K_{3}$ in the first $12 l$ columns along with $2 l C_{6}$ in the last three rows have a $(6; p, q)$ -decomposition as in Lemma 3.12. Also, the edges of $12 k C_{7}$ along with four columns of $2 k C_{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} K_{11}$ which has a $(6; p, q)$ -decomposition, by Lemma 3.4. Hence by Remark 1.3 $K_{m} K_{n}$ has a $(6; p, q)$ -decomposition.

Case 6. $m \equiv 5 (\mod 12), n \equiv 9 (\mod 12)$ .

Let $m = 12 k + 5, n = 12 l + 9$ . We can write $K_{m} K_{n} = n K_{m} \oplus m K_{n} = n ((K_{m} ∖ E (C_{4})) \oplus C_{4}) \oplus m K_{n}$ . Consider the first 5 rows and the last 2 rows as $K_{12 l + 1} \oplus K_{9} \oplus K_{12, 8}$ and $(K_{12 l + 1} ∖ E (2 l C_{6})) \oplus 2 l C_{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 $2 l C_{6}$ can be viewed as $2 l G$ , where $G = 6 C_{4} \oplus 2 C_{6} = C_{4}^{1} \oplus C_{4}^{2} \oplus \dots \oplus C_{4}^{6} \oplus C_{6}^{3} \oplus C_{6}^{4}$ with $V (G) = {x_{i, j} | 1 \leq i \leq 4, \leq j \leq 2}$ 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: ${(x_{3, 2 i} x_{3, (2 i - 1)} x_{2, (2 i - 1)} x_{1, (2 i - 1)} x_{4, (2 i - 1)} x_{4, 2 i} x_{3, 2 i}), (x_{3, 2 i} x_{2, 2 i} x_{1, 2 i} x_{4, 2 i} x_{4, (2 i + 1)} x_{3, (2 i + 1)} x_{3, 2 i})},$ where $1 \leq i \leq 6$ and the subscripts of $x$ are taken modulo 6 with residues ${1, \dots, 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_{12 l + 1} ∖ E (2 k C_{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) = {x_{i, j} | 1 \leq i \leq 5, \leq j \leq 6}$ 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} {(x_{1, 8} x_{1, 9} x_{5, 9} x_{5, 7} x_{2, 7} x_{2, 8} x_{1, 8}), (x_{1, 8} x_{4, 8} x_{3, 8} x_{2, 8} x_{2, 1} x_{1, 1} x_{1, 8})}, \\ {(x_{5, 5} x_{4, 5} x_{1, 5} x_{1, 7} x_{3, 7} x_{5, 7} x_{5, 5}), (x_{5, 5} x_{5, 3} x_{5, 2} x_{2, 2} x_{3, 2} x_{3, 5} x_{5, 5})}, \\ {(x_{3, 3} x_{2, 3} x_{2, 2} x_{2, 1} x_{4, 1} x_{3, 1} x_{3, 3}), (x_{3, 3} x_{3, 4} x_{2, 4} x_{1, 4} x_{4, 4} x_{4, 3} x_{3, 3})}, \\ {(x_{4, 2} x_{3, 2} x_{3, 1} x_{1, 1} x_{1, 3} x_{4, 3} x_{4, 2}), (x_{4, 2} x_{5, 2} x_{5, 4} x_{5, 9} x_{3, 9} x_{4, 9} x_{4, 2})}, \\ {(x_{4, 6} x_{4, 7} x_{4, 4} x_{3, 4} x_{3, 6} x_{1, 6} x_{4, 6}), (x_{4, 6} x_{2, 6} x_{2, 7} x_{1, 7} x_{1, 9} x_{4, 9} x_{4, 6})}, \\ (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} K_{n}$ .

Note 3.19. From Case 7 to Case 10 the degree of each vertex $v \in V (K_{m} K_{n})$ is odd and so $p \geq m n / 2$ .

Case 7. $m \equiv 0 (\mod 12)$ , $n \equiv i (\mod 12)$ , $i = 3, 5, 7, 11$ .

Let $m = 12 k$ and $n = 12 l + i$ , $l, k \in Z^{+}$ and $i \in {3, 5, 7, 11}$ . We can write $K_{m} K_{n} = n K_{m} \oplus m K_{n} = (n - i) K_{m} \oplus k (K_{i} K_{12}) \oplus i \frac{k (k - 1)}{2} K_{12, 12} \oplus m (K_{n} ∖ E (K_{i}))$ , $i \in {3, 5, 7, 11}$ . By Lemma 2.6, $K_{n} ∖ E (K_{i})$ has a $(6; p, q)$ -decomposition for $i = 3$ . For $i \in {5, 7, 11}$ , $K_{n} ∖ E (K_{i})$ can be viewed as $K_{12 l + 1} \oplus K_{12 l, 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} K_{12}$ , $i \in {3, 5, 7, 11}$ have a $(6; p, q)$ -decomposition. Hence by Remark 1.3, $K_{m} K_{n}$ has a $(6; p, q)$ -decomposition.

Case 8. $m \equiv 4 (\mod 12), n \equiv 3 o r 7 (\mod 12)$ .

Let $m = 12 k + 4$ . Then $K_{m} K_{n} = n K_{m} \oplus m K_{n} = n K_{m} \oplus m ((K_{n} ∖ 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} ∖ E (K_{3})$ has a $(6; p, q)$ -decomposition. Now, the last three columns can be viewed as $(K_{12 (k - 1)} ∖ 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)} ∖ 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) (6 K_{3} \oplus 3 C_{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} K_{16}$ and this has a $(6; p, q)$ -decomposition, by Lemma 3.5.

Case 9. $m \equiv 8 (\mod 12), n \equiv 3 (\mod 12)$ .

Let $m = 12 k + 8$ and $n = 12 l + 3$ . We can write $K_{m} K_{n} = n K_{m} \oplus m K_{n} = n ((K_{12 k} \oplus 2 C_{6}) \oplus (K_{8} ∖ E (2 C_{6})) \oplus K_{12 k, 8}) \oplus m ((K_{n} ∖ E (K_{3})) \oplus K_{3})$ , where $2 C_{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_{12 k} ∖ E (2 k C_{6})) \oplus 2 k C_{6} \oplus K_{8} \oplus K_{12 k, 8}$ and first three rows can be viewed as $(K_{m} ∖ E (2 l C_{6} \oplus K_{3})) \oplus 2 l C_{6} \oplus K_{3}$ . The graph $12 k K_{3}$ in the last $12 k$ rows along with the last 3 columns of $2 k C_{6}$ can be viewed as $2 k (6 K_{3} \oplus 3 C_{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} K_{3}$ and by Lemma 3.3, which has a $(6; p, q)$ -decomposition. Also by Lemma 2.8, $K_{12 k} \oplus 2 C_{6}$ in the first $(n - 3)$ columns has a $(6; p, q)$ -decomposition. The remaining edges $K_{8} ∖ E (2 C_{6})$ in the first $12 l$ columns and $2 l C_{6}$ in first 3 rows form $(K_{8} ∖ E (2 C_{6})) C_{6}$ which has a $(6; p, q)$ -decomposition, by Lemma 3.16.

Case 10. $m \equiv 8 (\mod 12), n \equiv 9 (\mod 12)$ .

Let $m = 12 k + 8$ and $n = 12 l + 9$ . We can write $K_{m} K_{n} = n K_{m} \oplus m K_{n} = (n - 9) ((K_{12 k} \oplus 2 C_{6}) \oplus (K_{8} ∖ E (2 C_{6})) \oplus K_{12 k, 8}) \oplus 9 (K_{12 k} \oplus K_{8} \oplus K_{12 k, 8}) \oplus m K_{n}$ . The last 8 rows can be viewed as $K_{12 l + 1} ∖ E (2 l C_{6}) \oplus 2 l C_{6} \oplus K_{9} \oplus K_{12 l, 8}$ . Now, the graph $K_{8} ∖ E (2 C_{6})$ in each $(n - 9)$ columns along with $2 l C_{6}$ in last 8 rows forms $2 l ((K_{8} ∖ E (2 C_{6})) 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} 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.

Acknowledgement:

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).

References:

A. Abueida and T. O’Neil. Multidecomposition of λK_m into small cycles and claws. Bulletin of the Institute of Combinatorics and its Applications, 49:32–40, 2007.
A. A. Abueida and M. Daven. Multidesigns for graph-pairs of order 4 and 5. Graphs and Combinatorics, 19:433–447, 2003. https://doi.org/10.1007/s00373-003-0530-3.
A. A. Abueida and M. Daven. Multidecompositions of the complete graph. Ars Combinatoria, 72:17–22, 2004.
A. A. Abueida, M. Daven, and K. J. Roblee. Multidesigns of the λ-fold complete graph for graph-pairs of orders 4 and 5. The Australasian Journal of Combinatorics, 32:125–136, 2005.
J. Bondy. Urs murty graph theory with applications the macmillan press ltd. New York, 1976.
A. P. Ezhilarasi and A. Muthusamy. Decomposition of product graphs into paths and stars with three edges. Bulletin of the Institute of Combinatorics and its Applications, 87:47–74, 2019.
K. A. Farrell and D. A. Pike. 6-cycle decompositions of the cartesian product of two complete graphs. Utilitas Mathematica:115–128, 2003.
C.-M. Fu, Y.-L. Lin, S.-W. Lo, and Y.-F. Hsu. Decomposition of complete graphs into triangles and claws. Taiwanese Journal of Mathematics, 18(5):1563–1581, 2014. https://doi.org/10.11650/tjm.18.2014.3169.
S. Jeevadoss and A. Muthusamy. Decomposition of complete bipartite graphs into paths and cycles. Discrete Mathematics, 331:98–108, 2014. https://doi.org/10.1016/j.disc.2014.05.009.
S. Jeevadoss and A. Muthusamy. Decomposition of product graphs into paths and cycles of length four. Graphs and Combinatorics, 32:199–223, 2016. https://doi.org/10.1007/s00373-015-1564-z.
H. Priyadharsini and A. Muthusamy. Multidecomposition of K_m,m(λ). Bulletin of the Institute of Combinatorics and its Applications, 66:42–48, 2012.
T.-W. Shyu. Decomposition of complete graphs into paths and stars. Discrete Mathematics, 310(15-16):2164–2169, 2010. https://doi.org/10.1016/j.disc.2010.04.009.

[1] A. Abueida and T. O’Neil. Multidecomposition of λK_m into small cycles and claws. Bulletin of the Institute of Combinatorics and its Applications, 49:32–40, 2007.

[2] A. A. Abueida and M. Daven. Multidesigns for graph-pairs of order 4 and 5. Graphs and Combinatorics, 19:433–447, 2003. https://doi.org/10.1007/s00373-003-0530-3.

[3] A. A. Abueida and M. Daven. Multidecompositions of the complete graph. Ars Combinatoria, 72:17–22, 2004.

[4] A. A. Abueida, M. Daven, and K. J. Roblee. Multidesigns of the λ-fold complete graph for graph-pairs of orders 4 and 5. The Australasian Journal of Combinatorics, 32:125–136, 2005.

[5] J. Bondy. Urs murty graph theory with applications the macmillan press ltd. New York, 1976.

[6] A. P. Ezhilarasi and A. Muthusamy. Decomposition of product graphs into paths and stars with three edges. Bulletin of the Institute of Combinatorics and its Applications, 87:47–74, 2019.

[7] K. A. Farrell and D. A. Pike. 6-cycle decompositions of the cartesian product of two complete graphs. Utilitas Mathematica:115–128, 2003.

[8] C.-M. Fu, Y.-L. Lin, S.-W. Lo, and Y.-F. Hsu. Decomposition of complete graphs into triangles and claws. Taiwanese Journal of Mathematics, 18(5):1563–1581, 2014. https://doi.org/10.11650/tjm.18.2014.3169.

[9] S. Jeevadoss and A. Muthusamy. Decomposition of complete bipartite graphs into paths and cycles. Discrete Mathematics, 331:98–108, 2014. https://doi.org/10.1016/j.disc.2014.05.009.

[10] S. Jeevadoss and A. Muthusamy. Decomposition of product graphs into paths and cycles of length four. Graphs and Combinatorics, 32:199–223, 2016. https://doi.org/10.1007/s00373-015-1564-z.

[11] H. Priyadharsini and A. Muthusamy. Multidecomposition of K_m,m(λ). Bulletin of the Institute of Combinatorics and its Applications, 66:42–48, 2012.

[12] T.-W. Shyu. Decomposition of complete graphs into paths and stars. Discrete Mathematics, 310(15-16):2164–2169, 2010. https://doi.org/10.1016/j.disc.2010.04.009.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

Decomposition of the cartesian product of complete graphs into paths and cycles of length six

Abstract

1. Introduction

2. Base Constructions

3. $(6; p, q)$ -decomposition of $K_{m} K_{n}$

Acknowledgement:

References:

Information

Guidelines

CP Initiatives

Follow CP

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

Decomposition of the cartesian product of complete graphs into paths and cycles of length six

Abstract

1. Introduction

2. Base Constructions

3. (6;p,q)-decomposition of KmKn

Acknowledgement:

References:

Information

Guidelines

CP Initiatives

Follow CP

3. $(6; p, q)$ -decomposition of $K_{m} K_{n}$