Menu
Let \(P_n\) and \(K_n\) respectively denote a path and complete graph on \(n\) vertices. By a \(\{pH_{1}, qH_{2}\}\)-decomposition of a graph \(G\), we mean a decomposition of \(G\) into \(p\) copies of \(H_{1}\) and \(q\) copies of \(H_{2}\) for any admissible pair of nonnegative integers \(p\) and \(q\), where \(H_{1}\) and \(H_{2}\) are subgraphs of \(G\). In this paper, we show that for any admissible pair of nonnegative integers \(p\) and \(q\), and positive integer \(n \geq 4\), there exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_n\) if and only if \(3p+4q=\binom{n}{2}\), where \(S_4\) is a star with \(4\) edges.
All graphs considered here are finite. Let \(K_k\) denote a complete graph on \(k\) vertices. Let \(P_{k+1}, C_{k}\) and \(S_{k}(\cong K_{1,k})\) respectively denote a path, cycle and star each having \(k\) edges. Further, we denote a path on \(k+1\) vertices \(x_1, x_2,\ldots ,x_{k+1}\), and edges \(x_1x_2,\ldots, x_kx_{k+1}\) by \([x_{1}\ldots x_{k}x_{k+1}]\). If there are \(t\geq 1\) stars with same end vertices \(x_{1}, x_{2},\ldots, x_{k}\) and different centers \(y_{1}, y_{2},\ldots, y_{t},\) we denote it by \((y_{1}, y_{2},\ldots, y_{t};x_{1}, x_{2},\ldots, x_{k})\). Let \(\mathbb{Z}_+\) be the set of all positive integers. When \(x, y\in \mathbb{Z}\), we define \(\left\lfloor x\right\rfloor = \text{max} \{y | y\in \mathbb{Z},~y\leq x\}\) and \(\left\lceil x \right\rceil=\text{min}\{y |y \in \mathbb{Z},~y\geq x\}\).
A decomposition of a graph \(G\) is a partition of \(G\) into edge-disjoint subgraphs of \(G\). If the subgraphs in the decomposition are isomorphic to either a graph \(H_1\) or a graph \(H_2\), then it is called a \(\{H_{1}, H_{2}\}\)-decomposition of \(G\). We say that \(G\) has a \(\{pH_{1}, qH_{2}\}\)-decomposition of \(G\) if the decomposition contains \(p\) copies of \(H_1\) and \(q\) copies of \(H_2\) for all possible choices of \(p\) and \(q\). Different problems on graph decomposition have been studied for a century. In particular, the problem of decomposing a complete graph into cycles is the center of attraction of many of these studies (e.g., the work of Alspach and Gavlas [1] and its references).
The study of \(\{H_1,H_2\}\)-decomposition has been introduced by Abueida and Daven [2,3]. Moreover, Abueida and O’Neil [4] have settled the existence of \(\{H_1,H_2\}\)-decomposition of \(\lambda K_{m},\) when \(\{H_1,H_2\}=\{K_{1,n-1}, C_{n}\}\) for \(n = 3, 4, 5\). Priyadharsini and Muthusamy [5] gave necessary and sufficient condition for the existence of \(\{G_{n}, H_{n}\}\)-factorization of \(\lambda K_{n}\), where \(G_{n}, H_{n} \in \{C_{n}, P_{n}, S_{n-1}\}\). Many other results on decomposition of graphs into distinct subgraphs involving paths, cycles or stars have been proved in [6-9]. Recently, Fu, et al. [10] have found the necessary and sufficient conditions for the existence of decomposition of \(K_{n}\) into cycles and stars on four vertices. In this paper, we obtain necessary and sufficient conditions for the existence of a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_n\).
Let \(M(G)\) denote the set of all pairs \((p, q)\) such that there exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(G\) and we define the set \(I(n)\) in Table 1 which help us to show that \(M(K_n)=I(n)\) for all feasible values of \(n\).
| $$n $$ | $$I(n)$$ |
| $$0, 1, 3, 4 \pmod{6}$$ | $$\Big\{(p, q)~|~p=\frac{n(n-1)}{6}-4i, q=\frac{n(n-1)}{8}-\frac{3p}{4},~0 \leq i \leq \left\lfloor \frac{n(n-1)}{24} \right\rfloor\Big\}$$ |
| $$2, 5 \pmod{6}$$ | $$\Big\{(p, q)~|~p=\frac{n(n-1)-8}{6}-4i, q=\frac{n(n-1)}{8}-\frac{3p}{4},~0 \leq i \leq \left\lfloor \frac{n(n-1)-8}{24} \right\rfloor\Big\}$$ |
Remark 1. Let \(A+B=\{(x_{1}+y_{1}, x_{2}+y_{2}) ~|~(x_{1}, x_{2})\in A,~(y_{1}, y_{2})\in B\}\) and \(rA\) be the sum of \(r\) copies of \(A\). If \(G= G_{1} \oplus G_{2}\), where \(\oplus\) denotes edge disjoint sum of the subgraphs \(G_1\) and \(G_2\), then \(M(G) \supseteq M(G_1) + M(G_2)\).
To prove our main result we state some known results as follows.
Theorem 1. [11] Let \(k, n \in \mathbb{Z}_{+}\). Then \(K_n\) has a \(P_{k+1}\)-decomposition if and only if \(n\geq k+1\) and \(n(n-1)\equiv 0 \pmod{2k}\).
Theorem 2. [12,13] Let \(n, k \in \mathbb{Z}_{+}\). Then \(K_n\) has a \(S_k\)-decomposition if and only if \(2k\leq n\) and \(n(n-1)\equiv 0\pmod{2k}\).
Theorem 3. [13] Let \(m,n\in \mathbb{Z}_{+}\) with \(m\leq n\). Then \(K_{m,n}\) has an \(S_{k}\)-decomposition if and only if one of the following holds:
\(m\geq k\) and \(mn \equiv 0 \pmod{k}\);
\(m < k \leq n\) and \(n \equiv 0 \pmod{k}\) .
In this section, we provide some useful lemmas which are required in proving our main result. The proof of the Lemmas 1 to 10, are given in the Appendix.
Lemma 1. There exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_{m, 6}\), when \(m=2,4,6\).
Proof. Case 1. For \(m=2\).
Let \(V(K_{2,6})=(X_{1}, X_{2})\), where \(X_{1}=\{x_{1,1}, x_{1,2}\}\) and \(X_{2}=\{x_{2,i}~|~1\leq i \leq 6\}\). We exhibit the \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_{2,6}\) for \(p=4\) and \(q=0\) as \[[x_{1,1}x_{2,1}x_{1,2}x_{2,2}], [x_{1,1}x_{2,3}x_{1,2}x_{2,4}], [x_{2,2}x_{1,1}x_{2,6}x_{1,2}], [x_{1,2}x_{2,5}x_{1,1}x_{2,4}].\] Hence, \(M(K_{2, 6})=(4, 0)\).
Case 2. For \(m=4\).
Let \(V(K_{4,6})=(X_{1}, X_{2})\), where \(X_{1}=\{x_{1,i}~|~1\leq i \leq 4\}\) and \(X_{2}=\{x_{2,i}~|~1\leq i \leq 6\}\). We exhibit the \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_{4,6}\) as follows:
For \(p=0\) and \(q=6\):
By Theorem 3, we get the required stars.
For \(p=4\) and \(q=3\):
\([x_{1,1}x_{2,1}x_{1,2}x_{2,2}],
[x_{1,2}x_{2,3}x_{1,1}x_{2,2}], [x_{1,3}x_{2,1}x_{1,4}x_{2,2}],
[x_{1,4}x_{2,2}x_{1,3}x_{2,3}], (x_{2,4}, x_{2,5}, x_{2,6}; x_{1,1},
x_{1,2}, x_{1,3}, x_{1,4})\).
For \(p=8\) and \(q=0\):
The \(4P_4\) along with \([x_{1,1}x_{2,4}x_{1,2}x_{2,5}],
[x_{1,2}x_{2,6}x_{1,1}x_{2,5}]\), \([x_{1,3}x_{2,4}x_{1,4}x_{2,5}],
[x_{1,4}x_{2,5}x_{1,3}x_{2,6}]\) gives the required
paths.
Hence, \(M(K_{4, 6})=\{(0, 6), (4, 3), (8, 0)\}\).
Case 3. For \(m=6\).
We can write \(K_{6,6}=K_{2,6} \oplus K_{4,6}\). Then \(M(K_{6,6})\supseteq M(K_{2,6}) + M(K_{4,6})\supseteq (4, 0) + \{(0, 6), (4, 3), (8, 0)\}=\{(4, 6), (8, 3), (12, 0)\}\). By Theorem 3, we get \(9S_4\). Hence \(M(K_{6, 6})=\{(0, 9), (4, 6), (8, 3), (12, 0)\}\). ◻
Lemma 2. There exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_5\).
Proof. From the definition of \(I(n)\), we get \(I(5)=(2, 1)\). Let \(V(K_5)=\{x_{i}~|~1 \leq i \leq 5\}\). We exhibit the \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_{5}\) for \(p=2\) and \(q=1\) as \([x_{2}x_{4}x_{3}x_{5}]\), \([x_{3}x_{2}x_{5}x_{4}], (x_{1}; x_{2}, x_{3}, x_{4}, x_{5})\). Hence, \(M(K_5)=I(5)=(2, 1)\). ◻
Lemma 3. There exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_6\).
Proof. From the definition of \(I(n)\), we get \(I(6)=\{(1, 3), (5, 0)\}\). Let \(V(K_6)=\{x_{i}~|~1 \leq i \leq 6\}\). We exhibit the \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_{6}\) as follows:
\((1, 3)\): Let \(D\) be an arbitrary \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_{6}\). Suppose that \(p=1\) and let \(P_{4}^{1}=[x_{1}x_{2}x_{3}x_{4}]\) be the only \(P_4\) in \(D\). By our assumption \(H_{1}=K_{6}-E(P_{4}^{1})\) has an \(S_4\)-decomposition. Let \(d(x_i)\) is degree of \(x_i\). In \(H_{1}\) , \(d(x_{1})= d(x_{4})=4\), \(d(x_{2})=d(x_{3})=3\) and \(d(x_{5})=d(x_{6})=5\). It follows that, any three of \(\{x_{1}, x_{4}, x_{5}, x_{6}\}\) must be a center vertex of stars in the decomposition \(D\). Let \(S_{4}^{1}=(x_{1}; x_{3}, x_{4}, x_{5}, x_{6})\) be a star in \(H_1\). Then \(H_{2}=H_{1}-E(S_{4}^{1})\), we have \(d(x_{1})=0\), \(d(x_{2})=d(x_{4})=3\), \(d(x_{5})=d(x_{6})=4\) and \(d(x_{3})=2\). It follows that \(x_5\) and \(x_6\) must be center vertices of stars in the decomposition \(D\). Let \(S_{4}^{2}=(x_{5}; x_{2}, x_{3}, x_{4}, x_{6})\) in \(H_2\). Then \(H_{3}=H_{2}-E(S_{4}^{2})\), we have \(d(x_{1})=d(x_{5})=0\), \(d(x_{2})=d(x_{4})=2\), \(d(x_{3})=1\) and \(d(x_{6})=3\). Hence \(H_3\) can not have a \(S_4\)-decomposition, which is a contradiction. Hence \((p, q) \neq (1, 3)\).
\((5, 0)\): By Theorem 1, we get the required paths.
Hence, \(M(K_6)=I(6)=(5, 0)\). ◻
Lemma 4. There exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_7\).
Proof. From the definition of \(I(n)\), we get \(I(7)=\{(3, 3), (7, 0)\}\). Let \(V(K_7)=\{x_{i}~|~1 \leq i \leq 7\}\). We exhibit the \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_{7}\) as follows:
For \(p=3\) and \(q=3\):
\([x_{1}x_{2}x_{3}x_{4}],
[x_{4}x_{5}x_{6}x_{7}], [x_{5}x_{7}x_{4}x_{6}], (x_{3}; x_{1}, x_{5},
x_{6}, x_{7})\), \((x_{1}, x_{2};
x_{4}, x_{5}, x_{6},x_{7})\).
For \(p=7\) and \(q=0\):
By Theorem 1, we get the required paths.
Hence, \(M(K_7)=I(7)=\{(3, 3), (7, 0)\}\). ◻
Lemma 5. There exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_8\).
Proof. From the definition of \(I(n)\), we get \(I(8)=\{(0, 7), (4, 4), (8, 1)\}\). Let \(V(K_8)=\{x_{i}~|~1 \leq i \leq 8\}\). We exhibit the \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_{8}\) as follows:
For \(p=0\) and \(q=7\):
By Theorem 2, we get the required stars.
\(p=4\) and \(q=4\):
\([x_{1}x_{2}x_{8}x_{3}], [x_{2}x_{5}x_{3}x_{4}], [x_{6}x_{3}x_{1}x_{8}], [x_{1}x_{4}x_{2}x_{3}], (x_{4}; x_{5}, x_{6}, x_{7}, x_{8}), (x_{5}; x_{1}, x_{6}, x_{7}, x_{8}), (x_{6}; x_{1}, x_{2}, x_{7},\\ x_{8}), (x_{7}; x_{1}, x_{2}, x_{3}, x_{8})\).
For \(p=8\) and \(q=1\):
The \(4P_{4}\) along with \([x_{1}x_{5}x_{4}x_{8}], [x_{2}x_{6}x_{7}x_{4}], [x_{1}x_{6}x_{5}x_{7}],\) \([x_{4}x_{6}x_{8}x_{5}]\) gives the required paths and the \(1S_4\) is \((x_{7}; x_{1}, x_{2}, x_{3}, x_{8})\).
Hence, \(M(K_8)=I(8)=\{(0, 7), (4, 4), (8, 1)\}\). ◻
Lemma 6. There exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_9\).
Proof. From the definition of \(I(n)\), we get \(I(9)=\{(0, 9), (4, 6), (8, 3), (12, 0)\}\). Let \(V(K_9)=\{x_{i}~|~1 \leq i \leq 9\}\). We exhibit the \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_{9}\) as follows:
For \(p=0\) and \(q=9\):
By Theorem 2, we get the required stars.
For \(p=4\) and \(q=6\):
\([x_{1}x_{2}x_{5}x_{4}],
[x_{2}x_{4}x_{1}x_{5}], [x_{6}x_{8}x_{7}x_{9}], [x_{7}x_{6}x_{9}x_{8}],
(x_{3}; x_{1}, x_{2}, x_{4}, x_{5})\), \((x_{1}, x_{2},x_{3}, x_{4}, x_{5}; x_{6}, x_{7},
x_{8}, x_{9}).\)
For \(p=8\) and \(q=3\):
The \(4P_{4}\) with \([x_{1}x_{6}x_{2}x_{9}], [x_{1}x_{7}x_{3}x_{6}], [x_{3}x_{9}x_{1}x_{8}]\), \([x_{3}x_{8}x_{2}x_{7}]\) gives the required paths and \(3S_4\) are \((x_{3}; x_{1}, x_{2}, x_{4}, x_{5})\), \((x_{4}, x_{5}; x_{6}, x_{7}, x_{8}, x_{9})\).
\(p=12\) and \(q=0\):
By Theorem 1, we get the required paths.
Hence, \(M(K_9)=I(9)=\{(0, 9), (4, 6), (8, 3), (12, 0)\}\). ◻
Lemma 7. There exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_{10}\).
Proof. From the definition of \(I(n)\), we get \(I(10)=\{(3, 9), (7, 6), (11, 3), (15, 0)\}\). Let \(V(K_{10})=\{x_{i}~|~1 \leq i \leq 10\}\). We exhibit the \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_{10}\) as follows:
For \(p=3\) and \(q=9\):
\([x_{1}x_{2}x_{3}x_{4}], [x_{2}x_{4}x_{1}x_{3}], [x_{4}x_{5}x_{6}x_{7}], (x_{5}; x_{1}, x_{2}, x_{3}, x_{7})\), \((x_{6}, x_{7}, x_{8}, x_{9}, x_{10}; x_{1}, x_{2}, x_{3}, x_{4}), (x_{8}; x_{5}, x_{6}, x_{7},\\ x_{9}),\) \((x_{9}; x_{5}, x_{6}, x_{7}, x_{10}), (x_{10}; x_{5}, x_{6}, x_{7}, x_{8})\).
For \(p=7\) and \(q=6\):
The \(3P_4\) along with \([x_{1}x_{10}x_{2}x_{8}], [x_{3}x_{9}x_{1}x_{8}], [x_{2}x_{9}x_{4}x_{10}]\), \([x_{4}x_{8}x_{3}x_{10}]\) gives the required paths and \(6S_4\) are \((x_{6}, x_{7}; x_{1}, x_{2}, x_{3}, x_{4})\), \((x_{5}; x_{1}, x_{2}, x_{3}, x_{7}), (x_{8}; x_{5}, x_{6}, x_{7}, x_{9}), (x_{9}; x_{5}, x_{6}, x_{7}, x_{10})\), \((x_{10}; x_{5}, x_{6},x_{7}, x_{8})\).
For \(p=11\) and \(q=3\):
The \(7P_{4}\) along with \([x_{1}x_{5}x_{2}x_{6}], [x_{1}x_{7}x_{3}x_{6}], [x_{1}x_{6}x_{4}x_{7}]\), \([x_{2}x_{7}x_{5}x_{3}]\) gives the required paths and \(3S_4\) are \((x_{8}; x_{5}, x_{6}, x_{7}, x_{9})\), \((x_{9}; x_{5}, x_{6}, x_{7}, x_{10})\), \((x_{10}; x_{5}, x_{6}, x_{7}, x_{8})\).
For \(p=15\) and \(q=0\):
By Theorem 1, we get the required paths.
Hence, \(M(K_{10})=I(10)=\{(3, 9), (7, 6), (11, 3), (15, 0)\}\). ◻
Lemma 8. There exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_{11}\).
Proof. From the definition of \(I(n)\), we get \(I(11)=\{(1, 13), (5, 10), (9, 7), (13, 4), (17, 1)\}\). Let \(V(K_{11})=\{x_{i}~|~1 \leq i \leq 11\}\). We exhibit the \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_{11}\) as follows:
For \(p=1\) and \(q=13\):
\([x_{3}x_{1}x_{10}x_{9}], (x_{1}, x_{2}; x_{4}, x_{5}, x_{6}, x_{7}), (x_{3}, x_{4}, x_{5}, x_{7}; x_{8}, x_{9}, x_{10}, x_{11}), (x_{1}; x_{2}, x_{8}, x_{9}, x_{11}), (x_{2}; x_{3}, x_{9}, x_{10},\\ x_{11}), (x_{3}; x_{1}, x_{5}, x_{6}, x_{7}), (x_{4}; x_{1}, x_{2}, x_{3}, x_{5}), (x_{6}; x_{5}, x_{7}, x_{9}, x_{10}), (x_{8}; x_{2}, x_{6}, x_{9}, x_{10}), (x_{11}; x_{6}, x_{8}, x_{9}, x_{10})\).
For \(p=5\) and \(q=10\):
\([x_{1}x_{2}x_{3}x_{4}], [x_{4}x_{5}x_{6}x_{7}], [x_{5}x_{7}x_{4}x_{6}], [x_{8}x_{9}x_{10}x_{11}], [x_{9}x_{11}x_{8}x_{10}],\) \((x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}, x_{7}; x_{8}, x_{9}, x_{10},\\ x_{11}), (x_{1}, x_{2}; x_{4}, x_{5}, x_{6}, x_{7}),\) \((x_{3}; x_{1}, x_{5}, x_{6}, x_{7})\).
For \(p=9\) and \(q=7\):
The \(5P_{4}\) along with \([x_{2}x_{8}x_{3}x_{9}], [x_{2}x_{10}x_{3}x_{11}], [x_{2}x_{11}x_{1}x_{10}]\), \([x_{2}x_{9}x_{1}x_{8}]\) gives the required paths and last \(7S_4\) gives the required stars.
For \(p=13\) and \(q=4\):
The \(9P_{4}\) along with \([x_{5}x_{8}x_{6}x_{9}], [x_{5}x_{10}x_{6}x_{11}], [x_{5}x_{9}x_{4}x_{8}]\), \([x_{5}x_{11}x_{4}x_{10}]\) gives the required paths and \(4S_4\) are \((x_{1}, x_{2}; x_{4}, x_{5}, x_{6}, x_{7})\), \((x_{3}; x_{1}, x_{5}, x_{6}, x_{7}), (x_{7}; x_{8}, x_{9}, x_{10}, x_{11})\).
For \(p=17\) and \(q=1\):
The \(13P_{4}\) along with \([x_{5}x_{1}x_{3}x_{7}], [x_{1}x_{7}x_{2}x_{6}], [x_{3}x_{5}x_{2}x_{4}]\), \([x_{3}x_{6}x_{1}x_{4}]\) gives the required paths and the \(1S_4\) is \((x_{7}; x_{8}, x_{9}, x_{10}, x_{11})\).
Hence, \(M(K_{11})=I(11)=\{(1, 13), (5, 10), (9, 7), (13, 4), (17, 1)\}\). ◻
Lemma 9. There exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_{12}\).
Proof. From the definition of \(I(n)\), we get \(I(12)=\{(2, 15), (6, 12), (10, 9), (14, 6), (18, 3), (22, 0)\}\). We can write \(K_{12}=2K_{6} \oplus K_{6,6}\). By Remark 1, and Lemmas 1,3, we have \(M(K_{12})\supseteq 2 M(K_{6}) + M(K_{6,6})\supseteq (10, 0)+ \{(0, 9), (4, 6), (8, 3), (12, 0)\}= \{(10, 9), (14, 6), (18, 3), (22, 0)\}= I(12)-\{(2, 15), (6, 12)\}\). We can write \(K_{12}=K_{4} \oplus K_{8} \oplus K_{4, 8}\). Then by Theorems 1 and 3, the graphs \(K_4\) and \(K_{4, 8}\) have \(2P_4\) and \(8S_4\) respectively, and by Lemma 5 the graph \(K_8\) has a decomposition for the case \((p, q)\in \{(0, 7), (4,4)\}\). Hence \(M(K_{12})=I(12)=\{(2, 15), (6, 12), (10, 9), (14, 6), (18, 3), (22, 0)\}\). ◻
Lemma 10. There exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_{14}\).
Proof. From the definition of \(I(n)\), we get \(I(14)= \{(1, 22), (5, 19),\ldots ,(29, 1)\}\). We can write \(K_{14}= K_{8}\oplus K_{6}\oplus 2K_{4, 6}\). Then by Remark 1, and Lemmas 1,3 and 5 we have \(M(K_{14})\supseteq M(K_{8}) + M(K_{6}) + 2 M(K_{4, 6})=\{(0, 7), (4, 4), (8, 1)\} +(5, 0) + 2\{(0, 6), (4, 3), (8, 0)\}=\{(5, 19), (9, 16),\ldots ,(29, 1)\}=I(14)-(1, 22)\). Let \(V(K_{14})=\{x_{i}~|~1\leq i \leq 14\}\). Then the required decomposition for the case \((p, q)=(1, 22)\) is given as follows: \([x_{7}, x_{6}, x_{14}, x_{11}], (x_{1}; x_{2}, x_{11}, x_{12}, x_{14}), (x_{3}; x_{1}, x_{2}, x_{11}, x_{14}), (x_{4}; x_{1}, x_{2}, x_{3}, x_{5}), (x_{5}; x_{1}, x_{2}, x_{3}, x_{7}),(x_{6}; x_{5}, \\ x_{11}, x_{12}, x_{13}), (x_{8}; x_{5}, x_{6}, x_{7}, x_{9}), (x_{9}; x_{5}, x_{6}, x_{7}, x_{10}), (x_{10}; x_{5}, x_{6}, x_{7}, x_{8}), (x_{12}; x_{3}, x_{11}, x_{13}, x_{14}), (x_{13}; x_{1}, x_{3},\\ x_{11}, x_{14}), (x_{2}, x_{4}, x_{5}, x_{7}, x_{8}, x_{9}, x_{10}; x_{11}, x_{12}, x_{13}, x_{14}), (x_{6}, x_{7}, x_{8}, x_{9}, x_{10}; x_{1}, x_{2}, x_{3}, x_{4}).\)
Hence, \(M(K_{14})=I(14)= \{(1, 22),\ldots ,(29, 1)\}\). ◻
In this section, we prove that \(K_n\) can be decomposed into \(p\) copies of \(P_4\) and \(q\) copies of \(S_4\) for all positive integer \(n\geq 4\).
Lemma 11. Let \(p, q\in \mathbb{Z}_{+}\cup\{0\}\) and \(n \equiv 0 \pmod{6}\). There exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_n\) if and only if \(3p+4q=\) \({n}\choose{2}\), and \(n\geq 6\). That is, \(M(K_{6s})=I(6s)\), where \(s\in \mathbb{Z}_{+}\).
Proof. Necessity: The conditions \(3p+4q=\) \({n}\choose{2}\) and \(n\geq 6\) are trivial. That is, \(M(K_{6s})\subseteq I(6s)\). Sufficiency: We have to prove \(M(K_{6s})\supseteq I(6s)\). The proof is by induction on \(s\). If \(s = 1\), then \(M(K_{6}) = I(6)\), by Lemma \(\ref{l3}\). Since \(K_{6k+6} = K_{6k} \oplus K_6 \oplus K_{6k,6}= K_{6k} \oplus K_6 \oplus kK_{6,6}\). From the definition of \(I(n)\), we have
\[\begin{aligned} I(24r)&=\Biggl\{ (p, q){\Big|}p=\frac{(24r)(24r-1)}{6}-4i,~q=\frac{(24r)(24r-1)}{8}-\frac{3p}{4},\\ &~0 \leq i \leq \left\lfloor\frac{(24r)(24r-1)}{24}\right\rfloor\Biggr\},\\ &=\{(4x, 3y)| 0 \leq x\leq 24r^{2}-r,~y=(24r^{2}-r)-x \},\\ I(24r+6)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+6)(24r+5)}{6}-4i,~q=\frac{(24r+6)(24r+5)}{8}-\frac{3p}{4},\\ &~0 \leq i \leq \left\lfloor\frac{(24r+6)(24r+5)}{24}\right\rfloor\Biggl\},\\ &=\{(4x+1, 3y)| 0 \leq x\leq 24r^{2}+11r+1,~y=(24r^{2}+11r+1)-x\},\\ I(24r+12)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+12)(24r+11)}{6}-4i,~q=\frac{(24r+12)(24r+11)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+12)(24r+11)}{24}\right\rfloor\Biggl\},\\ &=\{(4x+2, 3y)| 0 \leq x\leq 24r^{2}+23r+5,~y=(24r^{2}+23r+5)-x\},\\ I(24r+18)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+18)(24r+17)}{6}-4i,~q=\frac{(24r+18)(24r+17)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+18)(24r+17)}{24}\right\rfloor\Biggl\},\\ &=\{(4x+3, 3y)| 0 \leq x\leq 24r^{2}+35r+12,~y=(24r^{2}+35r+12)-x\},\\ I(24r+24)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+24)(24r+23)}{6}-4i,~q=\frac{(24r+24)(24r+23)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+24)(24r+23)}{24}\right\rfloor\Biggl\},\\ &=\{(4x, 3y)| 0 \leq x\leq 24r^{2}+47r+23,~y=(24r^{2}+47r+23)-x\}. \end{aligned}\]
Case 1. If \(k = 4r\), then we can write \(K_{24r+6} = K_{24r} \oplus K_6 \oplus (4r)K_{6,6}\). By the induction hypothesis, Remark 1.1, and Lemmas \(\ref{l1}\), \(\ref{l3}\), we have \(M(K_{24r+6}) \supseteq M(K_{24r}) + M(K_6) + (4r) M(K_{6,6})\)\(=\{(4x, 3y)| 0 \leq x\leq 24r^{2}-r,~y=(24r^{2}-r)-x\} + (5, 0) + (4r) \{(0, 9), (4, 6), (8, 3), (12, 0)\} =\{(4u+1, 3v)| 1 \leq u\leq 24r^{2}+11r+1,~v=(24r^{2}+11r+1)-u\}\)\(=I(24r+6)-\big(1, 3(24r^{2}+11r+1)\big)\). If \(r=1\), then \(K_{30} = K_{16} \oplus K_{14} \oplus K_{16,14}\). The graph \(K_{14}\) can be decomposed into \(1P_4\) and \(22S_4\), by Lemma 10, and the graphs \(K_{16}\) and \(K_{16,14}\) have an \(S_4\)-decomposition, by Theorems 2 and 3. Hence the graph \(K_{30}\) has a decomposition into \(1P_4\) and \(108S_4\). For \(r\geq 2\), we can write \(K_{24r+6} = K_{24r-8} \oplus K_{14} \oplus K_{24r-8,14}\). Then by Lemma 10, the graph \(K_{14}\) can be decomposed into \(1P_4\) and \(22S_4\), and by Theorems 2 and 3 , the graphs \(K_{24r-8}\) and \(K_{24r-8,14}\) have an \(S_4\)-decomposition. Hence the graph \(K_{24r+6}\) has a decomposition into \(1P_4\) and \(3(24r^{2}+11r+1)S_4\). Therefore \(M(K_{24r+6})=\{(4x+1, 3y)| 0 \leq x\leq 24r^{2}+11r+1,~y=(24r^{2}+11r+1)-x\}= I(24r+6)\).
Case 2. If \(k = 4r+1\), then we can write \(K_{24r+12} = K_{24r+6} \oplus K_6 \oplus (4r+1)K_{6,6}\). By the induction hypothesis, Remark 1.1, and Lemmas \(\ref{l1}\), \(\ref{l3}\), we have \(M(K_{24r+12}) \supseteq M(K_{24r+6}) + M(K_6) + (4r+1) M(K_{6,6})= \{(4x+1, 3y)| 0 \leq x\leq 24r^{2}+11r+1,~y=(24r^{2}+11r+1)-x\} + (5, 0) + (4r+1) \{(0, 9), (4, 6), (8, 3), (12, 0)\} =\{(4u+2, 3v)| 1 \leq u\leq 24r^{2}+23r+5,~v=(24r^{2}+23r+5)-u\}= I(24r+12)-\big(2, 3(24r^{2}+23r+5)\big)\). Let \(K_{24r+12} = K_{24r} \oplus K_{12} \oplus K_{24r,12}\). The graph \(K_{12}\) can be decomposed into \(2P_4\) and \(15S_4\), by Lemma 9, and by Theorems 2 and 3, the graphs \(K_{24r}\) and \(K_{24r,12}\) have an \(S_4\)-decomposition. Hence the graph \(K_{24r+12}\) has a decomposition into \(2P_4\) and \(3(24r^{2}+23r+5)S_4\). Therefore \(M(K_{24r+12})=\{(4x+2, 3y)| 0 \leq x\leq 24r^{2}+23r+5,~y=(24r^{2}+23r+5)-x\}= I(24r+12)\).
Case 3. If \(k = 4r+2\), then we can write \(K_{24r+18} = K_{24r+12} \oplus K_6 \oplus (4r+2)K_{6,6}\). By the induction hypothesis, Remark 1.1, and Lemmas 1,3, we have \(M(K_{24r+18}) \supseteq M(K_{24r+12}) + M(K_6) + (4r+2) M(K_{6,6})= \{(4x+2, 3y)| 0 \leq x\leq 24r^{2}+23r+5,~y=(24r^{2}+23r+5)-x\} + (5, 0) + (4r+2) \{(0, 9), (4, 6), (8, 3), (12, 0)\} =\{(4u+3, 3v)| 1\leq u\leq 24r^{2}+35r+12,~v=(24r^{2}+35r+12)-u\}= I(24r+18)-\big(3, 3(24r^{2}+35r+12)\big)\). Let \(K_{24r+18} = K_{24r+8} \oplus K_{10} \oplus K_{24r+8,10}\). The graph \(K_{10}\) can be decomposed into \(3P_4\) and \(9S_4\), by Lemma 7, and by Theorems 2 and 3 , the graphs \(K_{24r+8}\) and \(K_{24r+8,10}\) have an \(S_4\)-decomposition. Hence the graph \(K_{24r+18}\) has a decomposition into \(3P_4\) and \(3(24r^{2}+35r+12)S_4\). Therefore \(M(K_{24r+18})=\{(4x+3, 3y)| 0 \leq x\leq 24r^{2}+35r+12,~y=(24r^{2}+35r+12)-x\}= I(24r+18)\).
Case 4. If \(k = 4r+3\), then we can write \(K_{24r+24} = K_{24r+18} \oplus K_6 \oplus (4r+3)K_{6,6}\). By the induction hypothesis, Remark 1.1, and Lemmas 1,3, we have \(M(K_{24r+24}) \supseteq M(K_{24r+18}) + M(K_6) + (4r+3) M(K_{6,6})= \{(4x+3, 3y)| 0 \leq x\leq 24r^{2}+35r+12,~y=(24r^{2}+35r+12)-x\} + (5, 0) + (4r+3) \{(0, 9), (4, 6), (8, 3), (12, 0)\} =\{(4u, 3v)| 2 \leq u\leq 24r^{2}+47r+23,~v=(24r^{2}+47r+23)-u\}= I(24r+24)-\big\{\big(0, 3(24r^{2}+47r+23)\big), \big(4, 3(24r^{2}+47r+22)\big)\big\}\). The graph \(K_{24r+24}\) has \(3(24r^{2}+47r+23)S_4\), by Theorem 3, and hence \(M(K_{24r+24})=I(24r+24)-\big(4, 324r^{2}+47r+23)\). Let \(K_{24r+24} = K_{24r+16} \oplus K_{8} \oplus K_{24r+16,8}\). Then by Lemma 5, the graph \(K_{8}\) can be decomposed into \(4P_4\) and \(4S_4\), and by Theorems 2 and 3, the graphs \(K_{24r+16}\) and \(K_{24r+16,8}\) have an \(S_4\)-decomposition. Hence the graph \(K_{24r+24}\) has a decomposition into \(4P_4\) and \(3(24r^{2}+47r+22)S_4\). Therefore \(M(K_{24r+24})=\{(4x, 3y)| 0 \leq x\leq 24r^{2}+47r+23,~y=(24r^{2}+47r+23)-x\}= I(24r+24)\).
Thus \(M(K_{6s})=I(6s)\), for each \(s\in \mathbb{Z}_{+}\). ◻
Lemma 12. Let \(p, q\in \mathbb{Z}_{+}\cup\{0\}\) and \(n \equiv 1 \pmod{6}\). There exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_n\) if and only if \(3p+4q=\) \({n}\choose{2}\) and \(n \geq 7\). That is, \(M(K_{6s+1})=I(6s+1)\), where \(s\in \mathbb{Z}_{+}\).
Proof. Necessity: The conditions \(3p+4q=\) \({n}\choose{2}\) and \(n\geq 6\) are trivial. That is, \(M(K_{6s+1}) \subseteq I(6s+1)\). Sufficiency: We have to prove \(M(K_{6s+1})\supseteq I(6s+1)\). The proof is by induction on \(s\). If \(s = 1\), then \(M(K_{7}) = I(7)\), by Lemma 4. Since \(K_{6k+7} = K_{6k+1} \oplus K_7 \oplus K_{6k,6}= K_{6k+1} \oplus K_7 \oplus kK_{6,6}\). From the definition of \(I(n)\), we have
\[\begin{aligned} I(24r+1)&=\Biggl\{ (p, q){\Big|}p=\frac{(24r+1)(24r)}{6}-4i,~q=\frac{(24r+1)(24r)}{8}-\frac{3p}{4},\\ &~0 \leq i \leq \left\lfloor\frac{(24r+1)(24r)}{24}\right\rfloor\Biggr\},\\ &=\{(4x, 3y)| 0 \leq x\leq 24r^{2}+r,~y=(24r^{2}+r)-x\},\\ I(24r+7)&= \Biggl\{(p, q){\Big|}p=\frac{(24r+7)(24r+6)}{6}-4i,~q=\frac{(24r+7)(24r+6)}{8}-\frac{3p}{4},\\ &~0 \leq i \leq \left\lfloor\frac{(24r+7)(24r+6)}{24}\right\rfloor\Biggl\},\\ &=\{(4x+3, 3y)| 0 \leq x\leq 24r^{2}+13r+1,~y=(24r^{2}+13r+1)-x\},\\ I(24r+13)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+13)(24r+12)}{6}-4i,~q=\frac{(24r+13)(24r+12)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+13)(24r+12)}{24}\right\rfloor\Biggl\},\\ &=\{(4x+2, 3y)| 0 \leq x\leq 24r^{2}+25r+6,~y=(24r^{2}+25r+6)-x\},\\ I(24r+19) &= \Biggl\{(p, q){\Big|}p=\frac{(24r+19)(24r+18)}{6}-4i,~q=\frac{(24r+19)(24r+18)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+19)(24r+18)}{24}\right\rfloor\Biggl\},\\ &=\{(4x+1, 3y)| 0 \leq x\leq 24r^{2}+37r+14,~y=(24r^{2}+37r+14)-x\}, \end{aligned}\]
\[\begin{aligned} I(24r+25)&= \Biggl\{(p, q){\Big|}p=\frac{(24r+25)(24r+24)}{6}-4i,~q=\frac{(24r+25)(24r+24)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+25)(24r+24)}{24}\right\rfloor\Biggl\},\\ &=\{(4x, 3y)| 0 \leq x\leq 24r^{2}+49r+25,~y=(24r^{2}+49r+25)-x\}. \end{aligned}\]
Case 1. If \(k =
4r\), then we can write \(K_{24r+7} =
K_{24r+1} \oplus K_7 \oplus (4r)K_{6,6}\). By the induction
hypothesis, Remark 1.1, and Lemmas 1,4, we have \(M(K_{24r+7}) \supseteq M(K_{24r+1}) + M(K_7) +
(4r) M(K_{6,6})= \{(4x, 3y)| 0 \leq x\leq 24r^{2}+r,~y=(24r^{2}+r)-x\} +
\{(3, 3), (7, 0)\} + (4r) \{(0, 9), (4, 6), (8, 3), (12,
0)\}\)
=\(\{(4u+3, 3v)| 0 \leq u\leq
24r^{2}+13r+1,~v=(24r^{2}+13r+1)-u\}= I(24r+7)\).
Case 2. If \(k = 4r+1\), then we can write \(K_{24r+13} = K_{24r+7} \oplus K_7 \oplus (4r+1)K_{6,6}\). By the induction hypothesis, Remark 1.1, and Lemmas1,4, we have \(M(K_{24r+13}) \supseteq M(K_{24r+7}) + M(K_7) + (4r+1) M(K_{6,6})= \{(4x+3, 3y)| 0 \leq x\leq 24r^{2}+13r+1,~y=(24r^{2}+13r+1)-x\} + \{(3, 3), (7, 0)\} + (4r+1) \{(0, 9), (4, 6), (8, 3), (12, 0)\} =\{(4u+2, 3v)| 1 \leq u\leq 24r^{2}+25r+6,~v=(24r^{2}+25r+6)-u\}= I(24r+13)-\big(2, 3(24r^{2}+25r+6)\big)\). Let \(K_{24r+13} = K_{24r+9} \oplus K_{4} \oplus (8r+3)K_{3,4}\). Then the graphs \(K_{24r+9}\) and \(K_{3, 4}\) have an \(S_4\)-decomposition, by Theorems 2 and 3, the graph \(K_4\) has \(2P_4\). Hence the graph \(K_{24r+13}\) has a decomposition into \(2P_4\) and \(3(24r^{2}+25r+6)S_4\). Therefore \(M(K_{24r+13})=\{(4x+2, 3y)| 0 \leq x\leq 24r^{2}+25r+6,~y=(24r^{2}+25r+6)-x\}= I(24r+13)\).
Case 3. If \(k = 4r+2\), then we can write \(K_{24r+19} = K_{24r+13} \oplus K_7 \oplus (4r+2)K_{6,6}\). By the induction hypothesis, Remark 1.1, and Lemmas1,4, we have \(M(K_{24r+19}) \supseteq M(K_{24r+13}) + M(K_7) + (4r+2) M(K_{6,6})= \{(4x+2, 3y)| 0 \leq x\leq 24r^{2}+25r+6,~y=(24r^{2}+25r+6)-x\} + \{(3, 3), (7, 0)\} + (4r+2) \{(0, 9), (4, 6), (8, 3), (12, 0)\} =\{(4u+1, 3v)|1 \leq u\leq 24r^{2}+37r+14,~v=(24r^{2}+37r+14)-u\}= I(24r+19)-\big(1, 3(24r^{2}+37r+14)\big)\). Let \(K_{24r+19} = K_{24r+8} \oplus K_{11} \oplus K_{24r+8,11}\). Then the graph \(K_{11}\) can be decomposed into \(1P_4\) and \(13S_4\), by Lemma 8, and Theorems 2 and 3, the graphs \(K_{24r+8}\) and \(K_{24r+8,11}\) have an \(S_4\)-decomposition. Hence the graph \(K_{24r+19}\) has a decomposition into \(1P_4\) and \(3(24r^{2}+37r+14)S_4\). Therefore \(M(K_{24r+19})=\{(4x+1, 3y)| 0 \leq x\leq 24r^{2}+37r+14,~y=(24r^{2}+37r+14)-x\}= I(24r+19)\).
Case 4. If \(k = 4r+3\), then we can write \(K_{24r+25} = K_{24r+19} \oplus K_7 \oplus (4r+3)K_{6,6}\). By the induction hypothesis, Remark 1.1, and Lemmas1,4, we have \(M(K_{24r+25}) \supseteq M(K_{24r+19}) + M(K_7) + (4r+3) M(K_{6,6})= \{(4x+1, 3y)| 0 \leq x\leq 24r^{2}+37r+14,~y=(24r^{2}+37r+14)-x\} + \{(3, 3), (7, 0)\} + (4r+3) \{(0, 9), (4, 6), (8, 3), (12, 0)\} =\{(4u, 3v)| 1 \leq u\leq 24r^{2}+49r+25,~v=(24r^{2}+49r+25)-u\}= I(24r+25)-\big(0, 3(24r^{2}+49r+25)\big)\). The graph \(K_{24r+25}\) has \(3(24r^{2}+49r+25)S_4\), by Theorem 3. Hence \(M(K_{24r+25})=\{(4x, 3y)| 0 \leq x\leq 24r^{2}+49r+25,~y=(24r^{2}+49r+25)-x\}=I(24r+25)\).
Thus \(M(K_{6s+1})=I(6s+1)\), for each \(s\in \mathbb{Z}_{+}\). ◻
Lemma 13. Let \(p, q\in \mathbb{Z}_{+}\cup\{0\}\) and \(n \equiv 2 \pmod{6}\). There exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_n\) if and only if \(3p+4q=\) \({n}\choose{2}\), \(n \geq 8\) and \(q\geq 1\). That is, \(M(K_{6s+2})=I(6s+2)\), where \(s\in \mathbb{Z}_{+}\).
Proof. Necessity: The conditions \(3p+4q=\) \({n}\choose{2}\) and \(n\geq 6\) are trivial. That is, \(M(K_{6s+2}) \subseteq I(6s+2)\). Then \(q\geq 1\), since by Theorem 1, the graph \(K_{6s+2}\) can not have a \(P_4\)-decomposition. Sufficiency: We have to prove \(M(K_{6s+2})\supseteq I(6s+2)\). The proof is by induction on \(s\). If \(s = 1\), then \(M(K_{8}) = I(8)\), by Lemma \(\ref{l5}\). Since \(K_{6k+8} = K_{6k+2} \oplus K_6 \oplus K_{6k+2,6}\). From the definition of \(I(n)\), we have
\[\begin{aligned} I(24r+2)&=\Biggl\{ (p, q){\Big|}p=\frac{(24r+2)(24r+1)-8}{6}-4i,~q=\frac{(24r+2)(24r+1)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+2)(24r+1)-8}{24}\right\rfloor\Biggr\},\\ &=\{(4x+3, 3y+1)| 0 \leq x\leq 24r^{2}+3r-1,~y=(24r^{2}+3r-1)-x\},\\ I(24r+8)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+8)(24r+7)-8}{6}-4i,~q=\frac{(24r+8)(24r+7)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+8)(24r+7)-8}{24}\right\rfloor\Biggl\},\\ &=\{(4x, 3y+1)| 0 \leq x\leq 24r^{2}+15r+2,~y=(24r^{2}+15r+2)-x\},\\ I(24r+14)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+14)(24r+13)-8}{6}-4i,~q=\frac{(24r+14)(24r+13)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+14)(24r+13)-8}{24}\right\rfloor\Biggl\},\\ &=\{(4x+1, 3y+1)| 0 \leq x\leq 24r^{2}+27r+7,~y=(24r^{2}+27r+7)-x\},\\ I(24r+20)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+20)(24r+19)-8}{6}-4i,~q=\frac{(24r+20)(24r+19)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+20)(24r+19)-8}{24}\right\rfloor\Biggl\},\\ &=\{(4x+2, 3y+1)| 0 \leq x\leq 24r^{2}+39r+15,~y=(24r^{2}+39r+15)-x\},\\ I(24r+26)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+26)(24r+25)-8}{6}-4i,~q=\frac{(24r+26)(24r+25)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+26)(24r+25)-8}{24}\right\rfloor\Biggl\},\\ &=\{(4x+3, 3y+1)| 0 \leq x\leq 24r^{2}+51r+26,~y=(24r^{2}+51r+26)-x\}. \end{aligned}\]
Case 1. If \(k = 4r\), then we can write \(K_{24r+8} = K_{24r+2} \oplus K_6 \oplus K_{24r+2,6}\). Since \(K_{24r+2,6}=K_{24r,6}\oplus K_{2,6}=(4r)K_{6,6} \oplus K_{2,6}\). Then \(K_{24r+8} = K_{24r+2} \oplus K_6 \oplus (4r)K_{6,6}\oplus K_{2,6}\). By the induction hypothesis, Remark 1.1, and Lemmas1,3, we have \(M(K_{24r+8}) \supseteq M(K_{24r+2}) + M(K_6) + (4r) M(K_{6,6}) + M(K_{2, 6})= \{(4x+3, 3y+1)| 0 \leq x\leq 24r^{2}+3r-1,~y=(24r^{2}+3r-1)-x\} + (5, 0) + (4r) \{(0, 9), (4, 6), (8, 3), (12, 0)\} + (4, 0) =\{(4u, 3v+1)| 3 \leq u\leq 24r^{2}+15r+2,~v=(24r^{2}+15r+2)-u\}= I(24r+8)-\big\{\big(0, 3(24r^{2}+15r+2)\big), \big(4, 3(24r^{2}+15r+1)\big), \big(8, 3(24r^{2}+15r)\big)\big\}\). The graph \(K_{24r+8}\) has \(3(24r^{2}+15r+2)S_4\), by Theorem 2, we have \(M(K_{24r+8})=I(24r+8)-\big\{\big(4, 3(24r^{2}+15r+1)\big), \big(8, 3(24r^{2}+15r)\big)\big\}\). Let \(K_{24r+8} = K_{24r} \oplus K_{8} \oplus K_{24r,8}\). Then by Lemma 5, the graph \(K_{8}\) can be decomposed into \(8P_4\) or \(4P_4\) and \(4S_4\), and by Theorems 2 and 3, the graphs \(K_{24r}\) and \(K_{24r,8}\) have an \(S_4\)-decomposition. Hence the graph \(K_{24r+8}\) has a decomposition into \(p\) copies of \(P_4\) and \(q\) copies of \(S_4\), where \((p, q)\in \big\{\big(0, 3(24r^{2}+15r+2)\big), \big(4, 3(24r^{2}+15r+1)\big), \big(8, 3(24r^{2}+15r)\big)\big\}\). Therefore \(M(K_{24r+8})=\{(4x, 3y+1)| 0 \leq x\leq 24r^{2}+15r+2,~y=(24r^{2}+15r+2)-x\}= I(24r+8)\).
Case 2. If \(k = 4r+1\), then we can write \(K_{24r+14} = K_{24r+8} \oplus K_6 \oplus K_{24r+8,6}\). Since \(K_{24r+8,6}=(6r+2) K_{4,6}\). Then \(K_{24r+14} = K_{24r+8} \oplus K_6 \oplus (6r+2)K_{4,6}\). By the induction hypothesis, Remark 1.1, and Lemmas \(\ref{l1}\), \(\ref{l3}\), we have \(M(K_{24r+14}) \supseteq M(K_{24r+8}) + M(K_6) + (6r+2) M(K_{4,6})= \{(4x, 3y+1)| 0 \leq x\leq 24r^{2}+15r+2,~y=(24r^{2}+15r+2)-x\} + (5, 0) + (6r+2) \{(0, 6), (4, 3), (8, 0)\} =\{(4u+1, 3v+1)| 1\leq u\leq 24r^{2}+27r+7,~v=(24r^{2}+27r+7)-u\}= I(24r+14)-\big(1, 3(24r^{2}+27r+7)\big)\). If \(r=0\), then \(M(K_{14})=I(14)\), by Lemma 10 . If \(r\geq 1\), we can write \(K_{24r+14} = K_{24r} \oplus K_{14} \oplus K_{24r,14}\). Then by Lemma 10, the graph \(K_{14}\) can be decomposed into \(1P_4\) and \(22S_4\), and by Theorems 2 and 3, the graphs \(K_{24r}\) and \(K_{24r,14}\) have an \(S_4\)-decomposition. Hence the graph \(K_{24r+14}\) has a decomposition into \(1P_4\) and \(3(24r^{2}+27r+7)S_4\). Therefore \(M(K_{24r+14})=\{(4x+1, 3y+1)| 0 \leq x\leq 24r^{2}+27r+7,~y=(24r^{2}+27r+7)-x\}= I(24r+14)\).
Case 3. If \(k = 4r+2\), then we can write \(K_{24r+20} = K_{24r+14} \oplus K_6 \oplus K_{24r+14,6}\). Since \(K_{24r+14,6}=(6r+2) K_{4,6}\oplus K_{6,6}\). Then \(K_{24r+20} = K_{24r+14} \oplus K_6 \oplus (6r+2) K_{4,6}\oplus K_{6,6}\). By the induction hypothesis, Remark 1.1, and Lemmas \(\ref{l1}\), \(\ref{l3}\), we have \(M(K_{24r+20}) \supseteq M(K_{24r+14}) + M(K_6) + (6r+2) M(K_{4,6})= \{(4x+1, 3y+1)| 0 \leq x\leq 24r^{2}+27r+7,~y=(24r^{2}+27r+7)-x\} + (5, 0) + (6r+2) \{(0, 6), (4, 3), (8, 0)\} =\{(4u+2, 3v+1)|1 \leq u\leq 24r^{2}+39r+15,~v=(24r^{2}+39r+15)-u\}= I(24r+20)-\big(2, 3(24r^{2}+39r+15)\big)\). Let \(K_{24r+20} = K_{24r+16} \oplus K_{4} \oplus K_{24r+16,4}\). Then by Theorems 2 and 3, the graphs \(K_{24r+16}\) and \(K_{24r+16,4}\) have an \(S_4\)-decomposition, and the graph \(K_{4}\) has \(2P_4\). Hence the graph \(K_{24r+20}\) has a decomposition into \(2P_4\) and \(3(24r^{2}+39r+15)S_4\). Therefore \(M(K_{24r+20})=\{(4x+2, 3y+1)| 0 \leq x\leq 24r^{2}+39r+15,~y=(24r^{2}+39r+15)-x\}= I(24r+20)\).
Case 4. If \(k = 4r+3\), then we can write \(K_{24r+26} = K_{24r+20} \oplus K_6 \oplus K_{24r+16,4}\). Since \(K_{24r+20,6}=(6r+5) K_{4,6}\). Then \(K_{24r+26} = K_{24r+20} \oplus K_6 \oplus (6r+5) K_{4,6}\). By the induction hypothesis, Remark 1.1, and Lemmas \(\ref{l1}\), \(\ref{l3}\), we have \(M(K_{24r+26}) \supseteq M(K_{24r+20}) + M(K_6) + (6r+5) M(K_{4,6})= \{(4x+2, 3y+1)| 0 \leq x\leq 24r^{2}+39r+15,~y=(24r^{2}+39r+15)-x\} + (5, 0) + (6r+5) \{(0, 6), (4, 3), (8, 0)\} =\{(4u+3, 3v+1)|1 \leq u\leq 24r^{2}+51r+26,~v=(24r^{2}+51r+26)-u\}= I(24r+26)-\big(3, 3(24r^{2}+51r+26)\big)\). Let \(K_{24r+26} = K_{24r+16} \oplus K_{10} \oplus K_{24r+16,10}\). Then by Lemma 7, the graph \(K_{10}\) can be decomposed into \(3P_4\) and \(7S_4\), and by Theorems 2 and 3, the graphs \(K_{24r+16}\) and \(K_{24r+16,10}\) have an \(S_4\)-decomposition. Hence the graph \(K_{24r+26}\) has a decomposition into \(3P_4\) and \(3(24r^{2}+51r+26)S_4\). Therefore \(M(K_{24r+26})=\{(4x+3, 3y+1)| 0 \leq x\leq 24r^{2}+51r+26,~y=(24r^{2}+51r+26)-x\}= I(24r+26)\).
Thus \(M(K_{6s+2})=I(6s+2)\), for each \(s\in \mathbb{Z}_{+}\). ◻
Lemma 14. Let \(p, q\in \mathbb{Z}_{+}\cup\{0\}\) and \(n \equiv 3 \pmod{6}\). There exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_n\) if and only if \(3p+4q=\) \({n}\choose{2}\) and \(n\geq 9\). That is, \(M(K_{6s+3})=I(6s+3)\), where \(s\in \mathbb{Z}_{+}\).
Proof. Necessity: The conditions \(3p+4q=\) \({n}\choose{2}\) and \(n\geq 6\) are trivial. That is, \(M(K_{6s+3}) \subseteq I(6s+3)\). Sufficiency: We have to prove \(M(K_{6s+3})\supseteq I(6s+3)\). The proof is by induction on \(s\). If \(s = 1\), then \(M(K_{9}) = I(9)\), by Lemma 6. Since \(K_{6k+9} = K_{6k+3} \oplus K_7 \oplus K_{6k+2,6}\). From the definition of \(I(n)\), we have
\[\begin{aligned} I(24r+3)&=\Biggl\{ (p, q){\Big|}p=\frac{(24r+3)(24r+2)}{6}-4i,~q=\frac{(24r+3)(24r+2)}{8}-\frac{3p}{4},\\ &~0 \leq i \leq \left\lfloor\frac{(24r+3)(24r+2)}{24}\right\rfloor\Biggr\},\\ &=\{(4x+1, 3y)| 0 \leq x\leq 24r^{2}+5r,~y=(24r^{2}+5r)-x\},\\ I(24r+9)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+9)(24r+8)}{6}-4i,~q=\frac{(24r+9)(24r+8)}{8}-\frac{3p}{4},\\ &~0 \leq i \leq \left\lfloor\frac{(24r+9)(24r+8)}{24}\right\rfloor\Biggl\},\\ &= \{(4x, 3y)| 0 \leq x\leq 24r^{2}+17r+3,~y=(24r^{2}+17r+3)-x\},\\ I(24r+15)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+15)(24r+14)}{6}-4i,~q=\frac{(24r+15)(24r+14)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+15)(24r+14)}{24}\right\rfloor\Biggl\},\\ &= \{(4x+3, 3y)| 0 \leq x\leq 24r^{2}+29r+8,~y=(24r^{2}+29r+8)-x\}, \end{aligned}\]
\[\begin{aligned} I(24r+21) &= \Biggl\{(p, q){\Big|}p=\frac{(24r+21)(24r+20)}{6}-4i,~q=\frac{(24r+21)(24r+20)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+21)(24r+20)}{24}\right\rfloor\Biggl\},\\ &= \{(4x+2, 3y)| 0 \leq x\leq 24r^{2}+41r+17,~y=(24r^{2}+41r+17)-x\},\\ I(24r+27)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+27)(24r+26)}{6}-4i,~q=\frac{(24r+27)(24r+26)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+27)(24r+26)}{24}\right\rfloor\Biggl\},\\ &=\{(4x+1, 3y)| 0 \leq x\leq 24r^{2}+53r+29,~y=(24r^{2}+53r+29)-x\}. \end{aligned}\]
Case 1. If \(k = 4r\), then we can write \(K_{24r+9} = K_{24r+3} \oplus K_7 \oplus K_{24r+2,6}\). Since \(K_{24r+2,6}=(6r)K_{4,6}\oplus K_{2,6}\). Then \(K_{24r+9} = K_{24r+3} \oplus K_7 \oplus (6r)K_{4,6}\oplus K_{2,6}\). By the induction hypothesis, Remark 1.1, and Lemmas 1,4, we have \(M(K_{24r+9}) \supseteq M(K_{24r+3}) + M(K_7) + (6r) M(K_{4,6}) + M(K_{2, 6})= \{(4x+1, 3y)| 0 \leq x\leq 24r^{2}+5r,~y=(24r^{2}+5r)-x\} + \{(3, 3), (7, 0)\} + (6r) \{(0, 6), (4, 3), (8, 0)\} + (4, 0) =\{(4u, 3v)|2 \leq u\leq 24r^{2}+17r+3,~v=(24r^{2}+17r+3)-u\}= I(24r+9)-\big\{\big(0, 3(24r^{2}+17r+3)\big), \big(4, 3(24r^{2}+17r+2)\big)\big\}\). The graph \(K_{24r+9}\) has \(3(24r^{2}+17r+3)S_4\), by Theorem 2, we have \(M(K_{24r+8})=I(24r+8)-\big(4, 3(24r^{2}+17r+2)\big)\). Let \(K_{24r+9} = K_{24r+1} \oplus K_{8} \oplus K_{24r+1,8}\). Then by Lemma 5, the graph \(K_{8}\) can be decomposed into \(4P_4\) and \(4S_4\), and by Theorems 2 and 3, the graphs \(K_{24r+1}\) and \(K_{24r+1,8}\) have an \(S_4\)-decomposition. Hence the graph \(K_{24r+9}\) has a decomposition into \(4P_4\) and \(3(24r^{2}+17r+2)S_4\). Therefore \(M(K_{24r+9})=\{(4x, 3y)| 0 \leq x\leq 24r^{2}+17r+3,~y=(24r^{2}+17r+3)-x\}= I(24r+9)\).
Case 2. If \(k = 4r+1\), then we can write \(K_{24r+15} = K_{24r+9} \oplus K_7 \oplus K_{24r+8,6}\). Since \(K_{24r+8,6}=(6r+2)K_{4,6}\). Then \(K_{24r+15} = K_{24r+9} \oplus K_7 \oplus (6r+2)K_{4,6}\). By the induction hypothesis, Remark 1.1, and Lemmas \(\ref{l1}\), \(\ref{l4}\), we have \(M(K_{24r+15}) \supseteq M(K_{24r+9}) + M(K_7) + (6r+2) M(K_{4,6})= \{(4x, 3y)| 0 \leq x\leq 24r^{2}+17r+3,~y=(24r^{2}+17r+3)-x\} + \{(3, 3), (7, 0)\} + (6r+2) \{(0, 6), (4, 3), (8, 0)\} =\{(4u+3, 3v)| 0 \leq u\leq 24r^{2}+29r+8,~v=(24r^{2}+29r+8)-u\}= I(24r+15)\).
Case 3. If \(k = 4r+2\), then we can write \(K_{24r+21} = K_{24r+15} \oplus K_7 \oplus K_{24r+15,6}\). Since \(K_{24r+15,6}=(6r+2) K_{4,6}\oplus K_{6,6}\), we have \(K_{24r+21} = K_{24r+15} \oplus K_7 \oplus (6r+2) K_{4,6}\oplus K_{6,6}\). By the induction hypothesis, Remark 1.1, and Lemmas1,4, we have \(M(K_{24r+21}) \supseteq M(K_{24r+15}) + M(K_7) + (6r+2) M(K_{4,6}) + M(K_{6,6})= \{(4x+3, 3y)| 0 \leq x\leq 24r^{2}+29r+8,~y=(24r^{2}+29r+8)-x\} + \{(3, 3), (7, 0)\} + (6r+2) \{(0, 6), (4, 3), (8, 0)\} +\{(0, 9), (4, 6), (8, 3), (12, 0)\} =\{(4u+2, 3v)| 1\leq u\leq 24r^{2}+41r+17,~v=(24r^{2}+41r+17)-u\}= I(24r+21)-\big(2, 3(24r^{2}+41r+17)\big)\). Let \(K_{24r+21} = K_{24r+17} \oplus K_{4} \oplus K_{24r+17,4}\). Then the graphs \(K_{24r+17}\) and \(K_{24r+17,4}\) have an \(S_4\)-decomposition, by Theorems 2 and 3, the graph \(K_{4}\) has \(2P_4\). Hence the graph \(K_{24r+21}\) has a decomposition into \(2P_4\) and \(3(24r^{2}+41r+17)S_4\). Therefore \(M(K_{24r+21})=\{(4x+2, 3y)| 0 \leq x\leq 24r^{2}+41r+17,~y=(24r^{2}+41r+17)-x\}= I(24r+21)\).
Case 4. If \(k = 4r+3\), then we can write \(K_{24r+27} = K_{24r+21} \oplus K_7 \oplus K_{24r+20,6}\). Since \(K_{24r+20,6}=(6r+5) K_{4,6}\). By the induction hypothesis, Remark 1.1, and Lemmas1,4, we have \(M(K_{24r+27}) \supseteq M(K_{24r+21}) + M(K_7) + (6r+5) M(K_{4,6})= \{(4x+2, 3y)| 0 \leq x\leq 24r^{2}+41r+17,~y=(24r^{2}+41r+17)-x\} + \{(3, 3), (7, 0)\} + (6r+5) \{(0, 6), (4, 3), (8, 0)\} =\{(4u+1, 3v)| 1 \leq u\leq 24r^{2}+53r+29,~v=(24r^{2}+53r+29)-u\}= I(24r+27)-\big(1, 3(24r^{2}+53r+29)\big)\). Let \(K_{24r+27} = K_{24r+16} \oplus K_{11} \oplus K_{24r+16,11}\). Then by Lemma 8, the graph \(K_{11}\) can be decomposed into \(1P_4\) and \(13S_4\), and by Theorems 2 and 3, the graphs \(K_{24r+16}\) and \(K_{24r+16,11}\) have an \(S_4\)-decomposition. Hence the graph \(K_{24r+27}\) has a decomposition into \(1P_4\) and \(3(24r^{2}+53r+29)S_4\). Therefore \(M(K_{24r+27})=\{(4x+1, 3y)| 0 \leq x\leq 24r^{2}+53r+29,~y=(24r^{2}+53r+29)-x\}= I(24r+27)\).
Thus \(M(K_{6s+3})=I(6s+3)\), for each \(s\in \mathbb{Z}_{+}\). ◻
Lemma 15. Let \(p, q\in \mathbb{Z}_{+}\cup\{0\}\) and \(n \equiv 4 \pmod{6}\). There exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_n\) if and only if \(3p+4q=\) \({n}\choose{2}\) and \(n\geq 4\). That is, \(M(K_{6s+4})=I(6s+4)\), where \(s\in \mathbb{Z}_{+}\).
Proof. Necessity: The conditions \(3p+4q=\) \({n}\choose{2}\) and \(n\geq 4\) are trivial. That is, \(M(K_{6s+4}) \subseteq I(6s+4)\). Sufficiency: We have to prove \(M(K_{6s+4})\supseteq I(6s+4)\). The proof is by induction on \(s\). If \(s=0\), then \(M(K_4) = I(4)\), by Theorem \(\ref{pt1}\). If \(s = 1\), then \(M(K_{10}) = I(10)\), by Lemma \(\ref{l7}\). Since \(K_{6k+10} = K_{6k+4} \oplus K_6 \oplus K_{6k+4,6}\). From the definition of \(I(n)\), we have
\[\begin{aligned} I(24r+4)&=\Biggl\{ (p, q){\Big|}p=\frac{(24r+4)(24r+3)}{6}-4i,~q=\frac{(24r+4)(24r+3)}{8}-\frac{3p}{4},\\ &~0 \leq i \leq \left\lfloor\frac{(24r+4)(24r+3)}{24}\right\rfloor\Biggr\},\\ &=\{(4x+2, 3y)| 0 \leq x\leq 24r^{2}+7r,~y=(24r^{2}+7r)-x\},\\ I(24r+10)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+10)(24r+9)}{6}-4i,~q=\frac{(24r+10)(24r+9)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+10)(24r+9)}{24}\right\rfloor\Biggl\},\\ &=\{(4x+3, 3y)| 0 \leq x\leq 24r^{2}+19r+3,~y=(24r^{2}+19r+3)-x\},\\ I(24r+16)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+16)(24r+15)}{6}-4i,~q=\frac{(24r+16)(24r+15)}{8} \end{aligned}\]
\[\begin{aligned} &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+16)(24r+15)}{24}\right\rfloor\Biggl\},\\ &=\{(4x, 3y)| 0 \leq x\leq 24r^{2}+31r+10,~y=(24r^{2}+31r+10)-x\},\\ I(24r+22) &= \Biggl\{(p, q){\Big|}p=\frac{(24r+22)(24r+21)}{6}-4i,~q=\frac{(24r+22)(24r+21)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+22)(24r+21)}{24}\right\rfloor\Biggl\},\\ &=\{(4x+1, 3y)| 0 \leq x\leq 24r^{2}+43r+19,~y=(24r^{2}+43r+19)-x\},\\ I(24r+28)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+28)(24r+27)}{6}-4i,~q=\frac{(24r+28)(24r+27)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+28)(24r+27)}{24}\right\rfloor\Biggl\},\\ &=\{(4x+2, 3y)| 0 \leq x\leq 24r^{2}+55r+31,~y=(24r^{2}+55r+31)-x\}. \end{aligned}\]
Case 1. If \(k = 4r\), then we can write \(K_{24r+10} = K_{24r+4} \oplus K_6 \oplus K_{24r+4,6}\). Since \(K_{24r+4,6}=4rK_{6,6}\oplus K_{4,6}\). Then \(K_{24r+10} = K_{24r+4} \oplus K_6 \oplus 4rK_{6,6}\oplus K_{4,6}\). By the induction hypothesis, Remark 1.1, and Lemmas 1,3, we have \(M(K_{24r+10}) \supseteq M(K_{24r+4}) + M(K_6) + (4r) M(K_{6,6}) + M(K_{4, 6})= \{(4x+2, 3y)| 0 \leq x\leq 24r^{2}+7r,~y=(24r^{2}+7r)-x\}+(5, 0) + (4r)\{(0, 9), (4, 6), (8, 3), (12, 0)\} +\{(0, 6), (4, 3), (8, 0)\}=\{(4u+3, 3v)|1 \leq u\leq 24r^{2}+19r+3,~v=(24r^{2}+19r+3)-u\}= I(24r+10)-\big(3, 3(24r^{2}+19r+3)\big)\). Let \(K_{24r+10} = K_{24r} \oplus K_{10} \oplus K_{24r,10}\). Then by Lemma 7, the graph \(K_{10}\) can be decomposed into \(3P_4\) and \(9S_4\), and by Theorems 2 and 3, the graphs \(K_{24r}\) and \(K_{24r,10}\) have an \(S_4\)-decomposition. Hence the graph \(K_{24r+10}\) has a decomposition into \(3P_4\) and \(3(24r^{2}+19r+3)S_4\). Therefore \(M(K_{24r+10})=\{(4x+3, 3y)| 0 \leq x\leq 24r^{2}+19r+3,~y=(24r^{2}+19r+3)-x\}= I(24r+10)\).
Case 2. If \(k = 4r+1\), then we can write \(K_{24r+16} = K_{24r+10} \oplus K_6 \oplus K_{24r+10,6}\). Since \(K_{24r+10,6}=(4r+1)K_{6,6} \oplus K_{4,6}\). Then \(K_{24r+16} = K_{24r+10} \oplus K_6 \oplus (4r+1)K_{6,6} \oplus K_{4,6}\). By the induction hypothesis, Remark 1.1, and Lemmas 1,3, we have \(M(K_{24r+16}) \supseteq M(K_{24r+10}) + M(K_6) + (4r+1) M(K_{6,6})+ M(K_{4,6})= \{(4x+3, 3y)| 0 \leq x\leq 24r^{2}+19r+3,~y=(24r^{2}+19r+3)-x\} + (5, 0) + (4r+1) \{(0, 9), (4, 6), (8, 3), (12, 0)\} +\{(0, 6), (4, 3), (8, 0)\}=\{(4u, 3v)| 2 \leq u\leq 24r^{2}+31r+10,~v=(24r^{2}+31r+10)-u\}= I(24r+16)-\big\{\big(0, 3(24r^{2}+31r+10)\big), \big(4, 3(24r^{2}+31r+9)\big)\big\}\). The graph \(K_{24r+16}\) has \(3(24r^{2}+31r+10)S_4\), by Theorem 2. Hence \(K_{24r+16} =I(24r+16)-\big(4, 3(24r^{2}+31r+9)\big)\). Let \(K_{24r+16} = K_{24r+8} \oplus K_{8} \oplus K_{24r+8,8}\). Then by Lemma 5, graph \(K_{8}\) can be decomposed into \(4P_4\) and \(6S_4\), and by Theorems 2 and 3, the graphs \(K_{24r+8}\) and \(K_{24r+8,8}\) have an \(S_4\)-decomposition. Hence the graph \(K_{24r+16}\) has a decomposition into \(4P_4\) and \(3(24r^{2}+31r+9)S_4\). Therefore \(M(K_{24r+16})=\{(4x, 3y)| 0 \leq x\leq 24r^{2}+31r+10,~y=(24r^{2}+31r+10)-x\}= I(24r+16)\).
Case 3. If \(k = 4r+2\), then we can write \(K_{24r+22} = K_{24r+16} \oplus K_6 \oplus K_{24r+16,6}\). Since \(K_{24r+16,6}=(4r+2) K_{6,6}\oplus K_{4,6}\). Then \(K_{24r+22} = K_{24r+16} \oplus K_6 \oplus (4r+2) K_{6,6}\oplus K_{4,6}\). By the induction hypothesis, Remark 1.1, and Lemmas 1,3, we have \(M(K_{24r+22}) \supseteq M(K_{24r+16}) + M(K_6) + (4r+2) M(K_{6,6}) + M(K_{4,6})= \{(4x, 3y)| 0 \leq x\leq 24r^{2}+31r+10,~y=(24r^{2}+31r+10)-x\} + (5, 0) + (4r+2) \{(0, 9), (4, 6), (8, 3), (12, 0)\} + \{(0, 6), (4, 3), (8, 0)\} =\{(4u+1, 3v)| 1 \leq u\leq 24r^{2}+43r+19,~v=(24r^{2}+43r+19)-u\}= I(24r+22)-\big(1, 3(24r^{2}+43r+19)\big)\).
Let \(K_{24r+22} = K_{24r+8} \oplus K_{14} \oplus K_{24r+8,14}\). Then by Lemma 10, the graph \(K_{14}\) can be decomposed into \(1P_4\) and \(22S_4\), and by Theorems 2 and 3, the graphs \(K_{24r+8}\) and \(K_{24r+8,14}\) have an \(S_4\)-decomposition. Hence the graph \(K_{24r+22}\) has a decomposition into \(1P_4\) and \(3(24r^{2}+43r+19)S_4\). Therefore \(M(K_{24r+22})=\{(4x+1, 3y)| 0 \leq x\leq 24r^{2}+43r+19,~y=(24r^{2}+43r+19)-x\}= I(24r+22)\).
Case 4. If \(k = 4r+3\), then we can write \(K_{24r+28} = K_{24r+22} \oplus K_6 \oplus K_{24r+22,6}\). Since \(K_{24r+22,6}=(4r+3) K_{6,6}\oplus K_{4,6}\). Then \(K_{24r+28} = K_{24r+22} \oplus K_6 \oplus (4r+3) K_{6,6}\oplus K_{4,6}\). By the induction hypothesis, Remark 1.1, and Lemmas \(\ref{l1}\), \(\ref{l3}\), we have \(M(K_{24r+28}) \supseteq M(K_{24r+22}) + M(K_6) + (4r+3) M(K_{6,6}) + M(K_{4,6})= \{(4x+1, 3y)| 0 \leq x\leq 24r^{2}+43r+19,~y=(24r^{2}+43r+19)-x\} + (5, 0) + (4r+3) \{(0, 9), (4, 6), (8, 3), (12, 0)\} + \{(0, 6), (4, 3), (8, 0)\} =\{(4u+2, 3v)| 1 \leq u\leq 24r^{2}+55r+31,~v=(24r^{2}+55r+31)-u\}= I(24r+28)-\big(2, 3(24r^{2}+55r+31)\big)\). Let \(K_{24r+28} = K_{24r+24} \oplus K_{4} \oplus K_{24r+24,4}\). Then by Theorems 2 and 3, the graphs \(K_{24r+24}\) and \(K_{24r+24,4}\) have an \(S_4\)-decomposition, the graph \(K_{4}\) has \(2P_4\). Hence the graph \(K_{24r+28}\) has a decomposition into \(2P_4\) and \(3(24r^{2}+55r+31)S_4\). Therefore \(M(K_{24r+28})=\{(4x+2, 3y)| 0 \leq x\leq 24r^{2}+55r+31,~y=(24r^{2}+55r+31)-x\}= I(24r+28)\).
Thus \(M(K_{6s+4})=I(6s+4)\), for each \(s\in \mathbb{Z}_{+}\). ◻
Lemma 16. Let \(p, q\in \mathbb{Z}_{+}\cup\{0\}\) and \(n \equiv 5 \pmod{6}\). There exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_n\) if and only if \(3p+4q=\) \({n}\choose{2}\), \(n\geq 5\) and \(q\geq 1\). That is, \(M(K_{6s+5})=I(6s+5)\), where \(s\in \mathbb{Z}_{+}\cup \{0\}\).
Proof. Necessity: The conditions \(3p+4q=\) \({n}\choose{2}\) and \(n\geq 5\) are trivial. That is, \(M(K_{6s+5}) \subseteq I(6s+5)\). Then \(q\geq 1\), since by Theorem 1, the graph \(K_{6s+5}\) can not have a \(P_4\)-decomposition. Sufficiency: We have to prove \(M(K_{6s+5})\supseteq I(6s+5)\). The proof is by induction on \(s\). If \(s =0\), then \(M(K_{5}) = I(5)\), by Lemma 5. Since \(K_{6k+11} = K_{6k+5} \oplus K_7 \oplus K_{6k+4,6}\). From the definition of \(I(n)\), we have
\[\begin{aligned} I(24r+5)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+5)(24r+4)-8}{6}-4i,~q=\frac{(24r+5)(24r+4)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+5)(24r+4)-8}{24}\right\rfloor\Biggr\}, \end{aligned}\]
\[\begin{aligned} &= \{(4x+2, 3y+1)| 0 \leq x\leq 24r^{2}+9r,~y=(24r^{2}+9r)-x\},\\ I(24r+11)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+11)(24r+10)-8}{6}-4i,~q=\frac{(24r+11)(24r+10)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+11)(24r+10)-8}{24}\right\rfloor\Biggl\},\\ &= \{(4x+1, 3y+1)| 0 \leq x\leq 24r^{2}+21r+4,~y=(24r^{2}+21r+4)-x\},\\ I(24r+17)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+17)(24r+16)-8}{6}-4i,~q=\frac{(24r+17)(24r+16)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+17)(24r+16)-8}{24}\right\rfloor\Biggl\},\\ &= \{(4x, 3y+1)| 0 \leq x\leq 24r^{2}+33r+11,~y=(24r^{2}+33r+11)-x\},\\ I(24r+23)&= \Biggl\{(p, q){\Big|}p=\frac{(24r+23)(24r+22)-8}{6}-4i,~q=\frac{(24r+23)(24r+22)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+23)(24r+22)-8}{24}\right\rfloor\Biggl\},\\ &= \{(4x+3, 3y+1)| 0 \leq x\leq 24r^{2}+45r+20,~y=(24r^{2}+45r+20)-x\},\\ I(24r+29)&=\Biggl\{(p, q){\Big|}p=\frac{(24r+29)(24r+28)-8}{6}-4i,~q=\frac{(24r+29)(24r+28)}{8}\\ &~-\frac{3p}{4},~0 \leq i \leq \left\lfloor\frac{(24r+29)(24r+28)-8}{24}\right\rfloor\Biggl\},\\ &=\{(4x+2, 3y+1)| 0 \leq x\leq 24r^{2}+57r+33,~y=(24r^{2}+57r+33)-x\}. \end{aligned}\]
Case 1. If \(k = 4r\), then we can write \(K_{24r+11} = K_{24r+5} \oplus K_7 \oplus K_{24r+4,6}\). Since \(K_{24r+4,6}=(6r+1)K_{4,6}\). Then \(K_{24r+11} = K_{24r+5} \oplus K_7 \oplus (6r+1)K_{4,6}\). By the induction hypothesis, Remark 1.1, and Lemmas 1,3, we have \(M(K_{24r+11}) \supseteq M(K_{24r+5}) + M(K_7) + (6r+1) M(K_{4,6})= \{(4x+2, 3y+1)| 0 \leq x\leq 24r^{2}+9r,~y=(24r^{2}+9r)-x\} + \{(3, 3), (7, 0)\} + (6r+1) \{(0, 6), (4, 3), (8, 0)\}=\{(4u+1, 3v+1)| 1 \leq u\leq 24r^{2}+21r+4,~v=(24r^{2}+21r+4)-u\}= I(24r+11)-\big(1, 3(24r^{2}+21r+4)\big)\). Let \(K_{24r+11} = K_{24r} \oplus K_{11} \oplus K_{24r,11}\). Then by Lemma 8, the graph \(K_{11}\) can be decomposed into \(1P_4\) and \(13S_4\), and by Theorems 2 and 3, the graphs \(K_{24r}\) and \(K_{24r,11}\) have an \(S_4\)-decomposition. Hence the graph \(K_{24r+11}\) has a decomposition into \(1P_4\) and \(3(24r^{2}+21r+4)S_4\). Therefore \(M(K_{24r+11})=\{(4x+1, 3y+1)| 0 \leq x\leq 24r^{2}+21r+4,~y=(24r^{2}+21r+4)-x\}= I(24r+11)\).
Case 2. If \(k = 4r+1\), then we can write \(K_{24r+17} = K_{24r+11} \oplus K_7 \oplus K_{24r+10,6}\). Since \(K_{24r+10,6}=(6r+1)K_{4,6}\oplus K_{6,6}\). Then \(K_{24r+17} = K_{24r+11} \oplus K_7 \oplus (6r+1)K_{4,6}\oplus K_{6,6}\). By the induction hypothesis, Remark 1.1, and Lemmas 1,4, we have \(M(K_{24r+17}) \supseteq M(K_{24r+11}) + M(K_7) + (6r+1) M(K_{4,6}) + M(K_{6,6})= \{(4x+1, 3y+1)| 0 \leq x\leq 24r^{2}+21r+4,~y=(24r^{2}+21r+4)-x\} + \{(3, 3), (7, 0)\} + (6r+1) \{(0, 6), (4, 3), (8, 0)\} + \{(0, 9), (4, 6), (8, 3), (12, 0)\} = \{(4u, 3v+1)| 1 \leq u\leq 24r^{2}+33r+11,~v=(24r^{2}+33r+11)-u\}= I(24r+17)-\big(0, 3(24r^{2}+33r+11)\big)\). The graph \(K_{24r+17}\) has an \(S_4\)-decomposition, by Theorem 2. Hence \(M(K_{24r+17})=\{(4x, 3y+1)| 0 \leq x\leq 24r^{2}+33r+11,~y=(24r^{2}+33r+11)-x\}=I(24r+17)\)
Case 3. If \(k = 4r+2\), then we can write \(K_{24r+23} = K_{24r+17} \oplus K_7 \oplus K_{24r+16,6}\). Since \(K_{24r+16,6}=(6r+4) K_{4,6}\). Then \(K_{24r+23} = K_{24r+17} \oplus K_7 \oplus (6r+4) K_{4,6}\). By the induction hypothesis, Remark 1.1, and Lemmas 1,4, we have \(M(K_{24r+23}) \supseteq M(K_{24r+17}) + M(K_7) + (6r+4) M(K_{4,6})= \{(4x, 3y+1)| 0 \leq x\leq 24r^{2}+33r+11,~y=(24r^{2}+33r+11)-x\} + \{(3, 3), (7, 0)\} + (6r+4) \{(0, 6), (4, 3), (8, 0)\} =\{(4u+3, 3v+1)| 0 \leq u\leq 24r^{2}+45r+20,~v=(24r^{2}+45r+20)-u\}= I(24r+23)\).
Case 4. If \(k = 4r+3\), then we can write \(K_{24r+29} = K_{24r+23} \oplus K_7 \oplus K_{24r+22,6}\). Since \(K_{24r+22,6}=(6r+4) K_{4,6}\oplus K_{6,6}\). By the induction hypothesis, Remark 1.1, and Lemmas 1,4, we have \(M(K_{24r+29}) \supseteq M(K_{24r+23}) + M(K_7) + (6r+4) M(K_{4,6}) + M(K_{6,6})= \{(4x+3, 3y+1)| 0 \leq x\leq 24r^{2}+45r+20,~y=(24r^{2}+45r+20)-x\} + \{(3, 3), (7, 0)\} + (6r+4) \{(0, 6), (4, 3), (8, 0)\} + \{(0, 9), (4, 6), (8, 3), (12, 0)\} = \{(4u+2, 3v+1)| 1 \leq u\leq 24r^{2}+57r+33,~v=(24r^{2}+57r+33)-u\}= I(24r+29)-\big(2, 3(24r^{2}+57r+33)\big)\). Let \(K_{24r+29} = K_{24r+25} \oplus K_{4} \oplus K_{24r+25,4}\). Then by Theorems 2 and 3, the graphs \(K_{24r+25}\) and \(K_{24r+25,4}\) have an \(S_4\)-decomposition, the graph \(K_{4}\) has \(2P_4\). Hence the graph \(K_{24r+29}\) has a decomposition into \(2P_4\) and \(3(24r^{2}+57r+33)S_4\). Therefore \(M(K_{24r+29})=\{(4u+2, 3v+1)| 0 \leq u\leq 24r^{2}+57r+33,~v=(24r^{2}+57r+33)-u\}= I(24r+29)\).
Thus \(M(K_{6s+5})=I(6s+5)\), for each \(s\in \mathbb{Z}_{+}\cup \{0\}\). ◻
The consequences of Lemmas 11 to 6 implies our main result as follows.
Theorem 4. Let \(p\) and \(q\) are nonnegative integers, and \(n\geq 4\) be a positive integer. There exists a \(\{pP_{4}, qS_{4}\}\)-decomposition of \(K_n\) if and only if \(3p+4q=\) \({n}\choose{2}\). That is, \(M(K_{n})=I(n)\), where \(4\leq n\in \mathbb{Z}_{+}\).
Author’s thank the University Grants Commission, Government of India, New Delhi for its support through the Grant No.F.510/7/DRS-I/2016(SAP-I) and the anonymous referees whose suggestion improved the presentation of the paper.
Abueida, A. and Daven, M., 2003. Multidesigns for graph-pairs of order 4 and 5. Graphs and Combinatorics,19, pp.433–447.
Abueida, A. and Daven, M., 2004. Multidecomposition of the complete graph. Ars Combinatoria,72, pp.17–22.
Abueida, A. and O’Neil, T., 2007. Multidecomposition of \(\lambda K_m\) into small cycles and claws. Bulletin of the Institute of Combinatorics and its Applications,49, pp.32–40.
Priyadharsini, H. M. and Muthusamy, A., 2009. \((G_m, H_m)\)-Multifactorization of \(\lambda K_m\). Journal of Combinatorial Mathematics and Combinatorial Computing,69, pp.145–150.
Shyu, T.W., 2013. Decomposition of complete graphs into cycles and stars. Graphs and Combinatorics,29, pp.301–313.
Shyu, T.W., 2010. Decomposition of complete graphs into cycles and paths. Ars Combinatoria,97, pp.257–270.
Fu, C.M., Hsu, Y.F. and Lee, M.F., 2018. Decomposition of complete graphs into 4-cycles and 3-stars. Utilitas Mathematica,106, pp.271–288.
Tarsi, M., 1983. Decomposition of complete multigraph into simple paths: Nonbalanced Handcuffed designs. Journal of Combinatorial Theory, Series A,34, pp.60–70.
Tarsi, M., 1979. Decomposition of complete multigraph into stars. Discrete Mathematics, 26, pp.273–278.
Yamamoto, S., Ikeda, H., Shige-ede, S., Ushio, K. and Hamada, N. 1975. On claw decomposition of complete graphs and complete bipartite graphs. Hiroshima Mathematical Journal, 5, pp.33–42.