A \(\{P_5^{\alpha}, S_5^{\beta}, Y_5^{\gamma}\}\)-decomposition of a graph is a partition of its edge set into \(\alpha\) copies of \(P_5\), \(\beta\) copies of \(S_5\), and \(\gamma\) copies of \(Y_5\), where \(P_5\), \(S_5\), and \(Y_5\) denote the three non-isomorphic trees of order five. In this paper, we study the existence of a \(\{P_5^{\alpha}, S_5^{\beta}, Y_5^{\gamma}\}\)-decomposition of the complete bipartite graph \(K_{m,n}\) for \(m\geq 4\) and \(n\geq 2\), and of the complete graph \(K_n\) for \(n\geq 8\). In fact, we establish necessary and sufficient conditions for the existence of such decompositions in \(K_{m,n}\) and \(K_n\).
All graphs considered in this paper are finite, simple, and undirected. Let \(P_n\), \(S_n\), \(C_n\), \(K_n\), and \(K_{m,n}\) denote a path, a star, a cycle, a complete graph on \(n\) vertices, and a complete bipartite graph with partite sets of cardinalities \(m\) and \(n\), respectively. A \(Y\)-tree on five vertices, denoted by \(Y_5\), is the tree obtained from \(P_4\) by attaching a pendant vertex to a vertex of degree \(2\). A decomposition of a graph \(G\) is a partition of its edge set into subgraphs \(H_1,H_2,\dots,H_r\), where \(r\in\mathbb{N}\) and \(H_i\subseteq G\) for \(1\le i\le r\). If \(H_i\cong H\) for all \(1\le i\le r\), then \(G\) is said to be \(H\)-decomposable. If \(G\) can be decomposed into \(\alpha_i\ge 0\) copies of \(H_i\) for \(1\le i\le k\), then we say that \(G\) admits an \((H_1,H_2,\ldots,H_k)\)-multi-decomposition, or a \(\{H_1^{\alpha_1},H_2^{\alpha_2},\ldots,H_k^{\alpha_k}\}\)-decomposition. A \(k\)-tuple \((\alpha_1,\alpha_2,\ldots,\alpha_k)\) is said to be admissible if it satisfies the necessary condition for the existence of a \(\{H_1^{\alpha_1}, H_2^{\alpha_2},\ldots, H_k^{\alpha_k}\}\)-decomposition of \(G\), namely \[\sum\limits_{i=1}^{k}\alpha_i|E(H_i)|=|E(G)|.\] This condition is simply the edge-count, equivalently edge-divisibility, requirement, ensuring that the total number of edges contributed by the \(\alpha_i\) copies of each \(H_i\), for \(i=1,2,\dots,k\), equals \(|E(G)|\).
Graph decomposition is a well-established topic in graph theory. The concept of multi-decomposition was introduced by Abuieda and Devan [1]. Among the various structures used in decomposition, trees are particularly useful because of their simplicity and hierarchical nature [9, 14]. The decomposition of graphs into trees has a long history. Huang and Rosa [6] studied decompositions of complete graphs into various trees, including \(P_5\) and \(Y_5\). Cain [2] investigated decompositions of complete graphs into stars. Yamamoto et al. [19] established necessary and sufficient conditions for the decomposition of \(K_{m,n}\) into stars, while Parker [12] obtained necessary and sufficient conditions for the decomposition of \(K_{m,n}\) into paths. Joseph and Issacraj [13] established necessary and sufficient conditions for the decomposition of \(K_{m,n}\) into \(Y_5\)-trees, where the \(Y_5\)-tree is referred to as a fork. Shyu [17] obtained several results on \(\{P_k^\alpha,S_k^\beta\}\)-decomposition of \(K_{m,n}\) and \(K_n\). In addition, Shyu [18] determined necessary and sufficient conditions for the \(\{P_5^\alpha,S_5^\beta,C_5^\gamma\}\)-decomposition of \(K_{m,n}\) and \(K_n\). More recently, Ilayaraja and Muthusamy [7] established necessary and sufficient conditions for the existence of a \(\{P_4^\alpha, S_5^\beta\}\)-decomposition of \(K_n\).
Chaadhanaa and Hemalatha [3] established necessary and sufficient conditions for the existence of a \(\{P_5^\alpha,Y_5^\beta\}\)-decomposition of \(K_{m,n}\) and \(K_n\). Lin and Jou [11] studied \(\{C_k^\alpha,P_k^\beta,S_k^\gamma\}\)-decomposition of balanced complete bipartite multigraphs. Sethuraman and Murugan [16] proposed the conjecture that \(K_{4m+1}\), \(m\ge 1\), admits a \(\{H_1^\alpha,H_2^\beta\}\)-decomposition, where \(H_1\) and \(H_2\) are arbitrary trees of size \(m\). Lee and Chen [10] considered multi-decomposition of complete graphs into Hamiltonian paths and stars with three edges. Saranya et al. [15] studied \(\{S_{n-4}^\alpha,P_5^\beta\}\)-decomposition, for \(n\ge 5\), and \(\{S_{n-2}^\alpha,C_5^\beta\}\)-decomposition, for \(n\ge 4\), of \(n\)-dimensional hypercube graphs. Multi-decompositions of product graphs into trees were studied in [4, 5, 8]. In this paper, we focus on trees with four edges. There are three non-isomorphic trees of this size: the path \(P_5\), the star \(S_5\), and the \(Y\)-tree \(Y_5\). We determine necessary and sufficient conditions for the \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition of \(K_{m,n}\) and \(K_n\).
\(G=(\alpha_1,\alpha_2,\ldots,\alpha_k)\) indicates that \(G\) has a \(\{H_1^{\alpha_1},H_2^{\alpha_2},\ldots,H_k^{\alpha_k}\}\)-decomposition.
\(rG\) denotes \(r\) disjoint copies of the graph \(G\).
We write \(G=H_1\oplus H_2\) if \(G\) can be decomposed into \(H_1\) and \(H_2\).
The vertices of \(K_n\) are denoted by \(v_i\), \(1\le i\le n\).
The vertex partite sets of \(K_{m,n}\) are denoted by \(\{v_{1i}:1\le i\le m\}\) and \(\{v_{2j}:1\le j\le n\}\).
The path \(P_5\) with vertices \(v_i\), \(1\le i\le5\), having \(v_1\) and \(v_5\) as pendant vertices, is denoted by \((v_1,v_2,v_3,v_4,v_5)\).
The star \(S_5\) with vertices \(v_i\), \(1\le i\le5\), is denoted by \((v_1;v_2,v_3,v_4,v_5)\), where \(v_1\) is the center of \(S_5\).
The tree \(Y_5\) with vertices \(v_i\), \(1\le i\le5\), is denoted by \((v_1,v_2,\underline{v_3},v_4;\underline{v_5})\), where \(v_i\), \(1\le i\le4\), form a path of length three and the underlined vertices indicate the edge \(v_3v_5\). The vertex \(v_3\), which has degree three, is called the center of \(Y_5\).
Let \(\mathbb{N}_0\) denote the set of all non-negative integers. Then we define \[\mathbb{N}_0^k=\{(a_1,a_2,\ldots,a_k) \mid a_i \in \mathbb{N}_0,\; 1 \le i \le k\}.\]
Remark 1.1. Since each tree of order five contains four edges, the necessary condition given in the definition of admissible tuples becomes \[4\sum\limits_{i=1}^{k}\alpha_i=mn,\] where \(1\le k\le3\). Hence \(mn\equiv0\pmod{4}\). Since \(K_{m,n}\cong K_{n,m}\), any decomposition result established for \(K_{m,n}\) also holds for \(K_{n,m}\). Therefore, without loss of generality, in our treatment of complete bipartite graphs, we consider only the following arithmetic possibilities:
(i) \(m\equiv0\pmod{4}\) and \(n\ge2\);
(ii) \(m\equiv2\pmod{4}\) and \(n\equiv2\pmod{4}\), with \((m,n)\neq(2,2)\) since \(K_{2,2}\cong C_4\).
In this section, we obtain necessary and sufficient conditions for the \(\{S_5^{\alpha}, Y_5^{\beta}\}\)-decomposition of \(K_{m,n}\), where \(m\geq 4\) and \(n\geq 2\). We first recall some results required for the subsequent discussion.
Theorem 2.1([19]).Let \(k\), \(m\), and \(n\) be positive integers such that \(m\leq n\). There exists an \(S_{k+1}\)-decomposition of \(K_{m,n}\) if and only if one of the following conditions holds:
(i) \(k\leq m\) and \(mn\equiv0\pmod{k}\);
(ii) \(m<k\leq n\) and \(n\equiv0\pmod{k}\).
Theorem 2.2([13]).The complete bipartite graph \(K_{m,n}\) is \(Y_5\)-decomposable if and only if \[mn\equiv0\pmod{4},\] except for \(K_{2,4i+2}\), where \(i=1,2,\ldots\).
If \(X_1,\ldots,X_n\) are sets of ordered pairs of non-negative integers, then \[X_1+\cdots+X_n = \left\{ (p_1+\cdots+p_n,\, q_1+\cdots+q_n) :\, (p_i,q_i)\in X_i,\ 1\le i\le n \right\}.\]
Lemma 2.3. Suppose that \(n\ge2\) and \(m\ge3\). Let \[\{(p,q)\in\mathbb{N}_0^2:p+q=n,\ q\ne1\}\subseteq X_1\] and \[\{(a,b)\in\mathbb{N}_0^2:a+b=m,\ b\ne1\}\subseteq X_2.\] Define \[G_1:=\{(s,t)\in\mathbb{N}_0^2:s+t=n+m,\ t\ne1\}.\] Then \(G_1\subseteq X_1+X_2\).
Proof. It is easy to see that \((s,t)=(m+n-1,1)\notin X_1+X_2\). To prove the claim, it is enough to show that \[\label{eq1} \forall (s,t)\in G_1,\ \exists\ p_1,q_1,a_1,b_1\in\mathbb{N}_0: \begin{cases} (s,t)=(p_1+a_1,\ q_1+b_1),\\ p_1+q_1=n,\quad a_1+b_1=m,\\ q_1\neq1 \quad \text{and} \quad b_1\neq1. \end{cases} \tag{1}\]
Note that \(p_1,q_1\leq n\) and \(a_1,b_1\leq m\). The elements \(p_1,q_1,a_1,b_1\) satisfying the conditions given in (1) can be obtained in the following two cases.
Case 1. \(t=m+1\).
Then choose \[(p_1,q_1)=(n-2,2) \quad \text{and} \quad (a_1,b_1)=(1,m-1).\]
Case 2. \(t\neq m+1\).
In this case, let \[b_1=\min(t,m),\qquad a_1=m-b_1,\qquad q_1=t-b_1,\qquad p_1=n-q_1.\] It is clear that \(0\leq a_1,b_1\leq m\), \(a_1+b_1=m\), \(p_1\leq n\), \(q_1\geq0\), and \(p_1+q_1=n\).
Subclaim 1. \(q_1\leq n\).
If \(b_1=\min(t,m)=t\), then \(q_1=t-b_1=0\leq n\). If \(b_1=m\), then \(q_1\leq n\) because \[s+t=n+m \implies t\leq m+n \implies t-m\leq n.\]
Subclaim 2. \(p_1\geq0\).
Since \(q_1\leq n\) by Subclaim 1, it follows that \(p_1\geq0\). ◻
Corollary 2.4. Suppose that \(n,m\ge2\), \[\{(p,q)\in\mathbb{N}_0^2:p+q=n,\ q\ne1\}\subseteq X_3\] and \[\{(a,b)\in\mathbb{N}_0^2:a+b=m\}\subseteq X_4.\] Define \[G_2:=\{(s,t)\in\mathbb{N}_0^2:s+t=n+m\}.\] Then \(G_2\subseteq X_3+X_4\).
Proof. The elements \(p_1,q_1,a_1,b_1\) constructed in Lemma 2.3 remain valid for any \((s,t)\in G_2\) when \(m,n\ge2\), since no restriction on \(b\) is required in this case. Hence, \(G_2\subseteq X_3+X_4\). ◻
Lemma 2.5. There is no \(\{S_5^{n-1},Y_5^{1}\}\)-decomposition of \(K_{4,n}\), \(n\geq3\), whenever \(\alpha+\beta=n\).
Proof. Suppose that there exists a \(\{S_5^{n-1},Y_5^{1}\}\)-decomposition of \(G:=K_{4,n}\). Let \(G^1=K_{4,n}-Y_5\). The center of \(Y_5\) is either \(v_{2j}\), \(1\le j\le n\), or \(v_{1i}\), \(1\le i\le4\).
Case 1. \(Y_5\) has center at \(v_{2j}\).
Then the degree sequence of the vertices \(v_{1i}\) in \(G^1\) is \(\{n,n-1,n-1,n-2\}\). At least two of \(n\), \(n-1\), and \(n-2\) are not divisible by \(4\). Let \(v_{1k_1}\), \(1\le k_1\le4\), be a vertex whose degree is not a multiple of \(4\). Then at least one edge, say \(e_1\), incident with \(v_{1k_1}\) cannot belong to an \(S_5\) with center \(v_{1k_1}\). Hence \(e_1\) must lie in an \(S_5\) whose center is \(v_{2j_1}\), \(1\le j_1\le n\). Note that \(v_{2j_1}\) cannot be a vertex of \(Y_5\). Let \(S_5^1\) be the star containing \(e_1\). Then the degree sequence of the vertices \(v_{1i}\) in \(G^2:=G^1-S_5^1\) is \(\{n-1,n-2,n-2,n-3\}\). Again, at least two of \(n-1\), \(n-2\), and \(n-3\) are not divisible by \(4\). Let \(v_{1k_2}\), \(1\le k_2\le4\), be a vertex whose degree is not a multiple of \(4\). Then at least one edge, say \(e_2\), incident with \(v_{1k_2}\) cannot belong to an \(S_5\) with center \(v_{1k_2}\). Hence \(e_2\) must lie in an \(S_5\) whose center is \(v_{2j_2}\), \(1\le j_2\le n\), where \(v_{2j_2}\ne v_{2j_1}\) and \(v_{2j_2}\) is not a vertex of \(Y_5\). Let \(S_5^2\) be the star containing \(e_2\). Then the degree sequence of the vertices \(v_{1i}\) in \(G^3:=G^2-S_5^2\) is \(\{n-2,n-3,n-3,n-4\}\). Continuing this process, we obtain \(G^{n-1}:=G^{n-2}-S_5^{n-2}\) with degree sequence \(\{2,1,1,0\}\) for the vertices \(v_{1i}\). This degree sequence cannot yield an \(S_5\), which is a contradiction.
Case 2. \(Y_5\) has center at \(v_{1i}\).
The proof follows by the same argument as in Case 1. In this case, the degree sequence of \(v_{1i}\) in \(G\) is \(\{n,n,n-1,n-3\}\), and the degree sequence of \(v_{1i}\) in \(G^{n-2}\) is \(\{3,3,2,0\}\). Clearly, \(G^{n-2}\) cannot be decomposed into \(2S_5\), which gives a contradiction. Hence, \(K_{4,n}\) does not have a \(\{S_5^{n-1},Y_5^{1}\}\)-decomposition whenever \(\alpha+\beta=n\). ◻
Lemma 2.6. \(K_{4,n}\), \(n\geq3\), admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=n\), except when \((\alpha,\beta)=(n-1,1)\).
Proof. If \(\alpha=0\) or \(\beta=0\), then Theorems 2.1 and 2.2 give the required decompositions. For \(1\le \alpha\le n-2\), we write \[K_{4,n}=\alpha S_5\oplus K_{4,n-\alpha},\] where the center of each \(S_5\) is \(v_{2j}\), \(1\le j\le n\). By Theorem 2.2, \(K_{4,n-\alpha}=(n-\alpha)Y_5\). Therefore, \(K_{4,n}\) admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=n\) and \(\beta\ne1\). ◻
Remark 2.7. It is easy to see that \(K_{4,2}\) does not have a \(\{S_5^1,Y_5^1\}\)-decomposition whenever \(\alpha+\beta=2\). If \(\alpha=0\) or \(\beta=0\), then Theorems 2.1 and 2.2 give the required decompositions.
Lemma 2.8. There is no \(\{S_5^{3p-1},Y_5^{1}\}\)-decomposition of \(K_{4p,3}\) whenever \(\alpha+\beta=3p\).
Proof. Since the vertices \(v_{1i}\), \(1\le i\le4p\), have degree \(3\) in \(K_{4p,3}\), none of them can be the center of an \(S_5\). Hence, the center of every \(S_5\) must be a vertex \(v_{2j}\), \(1\le j\le3\). Each vertex \(v_{2j}\) can be the center of at most \(p\) stars. To obtain a decomposition of \(K_{4p,3}\) into \((3p-1)S_5\), two of the vertices \(v_{2j}\) would have to be centers of \(p\) stars each, using all their incident edges, while the remaining vertex \(v_{2j}\) would be the center of only \(p-1\) stars. Consequently, no edges would remain to form the required \(Y_5\). Therefore, \(K_{4p,3}\) admits no \(\{S_5^{3p-1},Y_5^1\}\)-decomposition whenever \(\alpha+\beta=3p\). ◻
Lemma 2.9. \(K_{4p,3}\) admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=3p\), except when \((\alpha,\beta)=(3p-1,1)\).
Proof. When \(n=3\), we write \[K_{4p,3}=pK_{4,3}.\] By Lemma 2.6, \(K_{4,3}\) admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=3\), except when \(\beta=1\). Hence, by Lemma 2.3, \(K_{4p,3}\) admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=3p\) and \(\beta\neq1\). ◻
Lemma 2.10. \(K_{8,i}\), \(i\in\{5,6\}\), admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=2i\).
Proof. We write \[K_{8,i}=2K_{4,i}.\] By Lemma 2.6, \(K_{4,i}\) admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=i\), except when \(\beta=1\). Hence, by Lemma 2.3, \(K_{8,i}\) admits a \(\{S_5^{\alpha},Y_5^{\beta}\}\)-decomposition whenever \(\alpha+\beta=2i\), except when \(\beta=1\). For \(\beta=1\), when \(i=5\), the edge set for the admissible pair \((9,1)\) is given by \[(v_{25}; v_{11}, v_{13}, v_{17}, v_{18}), \quad (v_{24}; v_{11}, v_{14}, v_{15}, v_{16}),\] \[(v_{12}; v_{22}, v_{23}, v_{24}, v_{25}), \quad (v_{13}; v_{21}, v_{22}, v_{23}, v_{24}),\] \[(v_{14}; v_{21}, v_{22}, v_{23}, v_{25}), \quad (v_{15}; v_{21}, v_{22}, v_{23}, v_{25}),\] \[(v_{16}; v_{21}, v_{22}, v_{23}, v_{25}), \quad (v_{17}; v_{21}, v_{22}, v_{23}, v_{24}),\] \[(v_{18}; v_{21}, v_{22}, v_{23}, v_{24}), \quad (v_{12}, v_{21}, \underline{v_{11}},v_{23};\underline{v_{22}}).\] When \(i=6\), we write \[K_{8,6}=2S_5\oplus K_{8,5},\] which gives \((11,1)=(2,0)+(9,1)\). Thus, \(K_{8,i}\), \(i\in\{5,6\}\), admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=2i\). ◻
Lemma 2.11. \(K_{4p,n}\), \(p\geq2\), \(n\geq5\), admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=pn\).
Proof. We write \[K_{4p,n}=K_{8,i}\oplus 2(K_{4,n-i})\oplus (p-2)K_{4,n},\] where \(i=5\) if \(n\) is odd and \(i=6\) if \(n\) is even. By Lemma 2.10, \(K_{8,i}\) admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=2i\). Further, by Lemma 2.6 and Remark 2.7, both \(K_{4,n-i}\) and \(K_{4,n}\) admit a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=n-i\) and \(\alpha+\beta=n\), respectively. Hence, by Lemma 2.3 and Corollary 2.4, \(K_{4p,n}\), \(p\geq2\), \(n\geq5\), admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=pn\). ◻
Lemma 2.12. There is no \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition of \(K_{2p,2}\), \(p>1\), whenever \(\alpha+\beta=p\) and one of the following holds:
(i) \(\beta\) is odd;
(ii) \(\beta=0\) and \(p\) is odd.
Proof. If \(\alpha=0\), or if \(\beta=0\) and \(p\) is odd, then Theorems 2.2 and 2.1, respectively, imply that no such decompositions exist. Now let \(\beta\in\{1,\ldots,p-1\}\) be odd. Suppose that \(K_{2p,2}\) admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition. Then the vertices \(v_{2j}\), \(j\in\{1,2\}\), must serve as centers of the trees in the decomposition. After removing \(\beta\) copies of \(Y_5\), each vertex \(v_{2j}\) has odd degree in \(K_{2p,2}-\beta Y_5\). Since \(v_{2j}\) must be the center of every \(S_5\), it follows that \(K_{2p,2}-\beta Y_5\) cannot be decomposed into \((p-\beta)S_5\), which is a contradiction. ◻
Remark 2.13. \(K_{6,2}\) admits an \((S_5^1,Y_5^2)\)-decomposition whenever \(\alpha+\beta=3\) and does not have an \((S_5^\alpha,Y_5^\beta)\)-decomposition for other possible admissible pairs by Lemma 2.12. For \((1,2)\), the edge sets are given by \[(v_{21};v_{11},v_{12},v_{13},v_{14}),\] \[(v_{21}, v_{15}, \underline{v_{22}}, v_{14}; \underline{v_{13}})\] and \[(v_{21}, v_{16}, \underline{v_{22}}, v_{11}; \underline{v_{12}}).\]
Lemma 2.14. \(K_{2p,2}\), \(p>1\), admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=p\), \(\beta\) is even, and \(\beta\ne0\) if \(p\) is odd.
Proof. When \(p\) is odd, let \(p=2p_1+1\) for some \(p_1\in\mathbb{N}\). We write \[K_{2p,2}=(p_1-1)K_{4,2}\oplus K_{6,2}.\] Take \(K_{6,2}=(1,2)\). Any even value of \(\beta\) such that \(2\leq\beta\leq p-1\) can be obtained by choosing appropriate admissible pairs between \((0,2)\) and \((2,0)\) of \(K_{4,2}\), which exist by Remark 2.7.
When \(p\) is even, let \(p=2p_1\) for \(p_1\in\mathbb{N}\). We write \[K_{2p,2}=p_1K_{4,2}.\] The proof follows by an argument similar to that for \(p\) odd. ◻
Lemma 2.15. \(K_{6,6}\) admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=9\).
Proof. If \(\alpha=0\) or \(\beta=0\), then Theorems 2.2 and 2.1, respectively, give the required decompositions. We write \[K_{6,6}=K_{6,4}\oplus K_{6,2}.\] Since \(K_{6,4}\cong K_{4,6}\), by Lemma 2.6, \(K_{6,4}\) has a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition for the admissible pairs \[(\alpha,\beta)\in \{(0,6),(1,5),(2,4),(3,3),(4,2),(6,0)\}.\] Take \(K_{6,2}=(1,2)\). Then, for each admissible pair \((\alpha,\beta)\) of \(K_{6,4}\), we obtain a corresponding admissible pair for \(K_{6,6}\) by addition, namely \((\alpha+1,\beta+2)\). This yields \[(\alpha,\beta)\in\{(1,8),(2,7),(3,6),(4,5),(5,4),(7,2)\}.\] For the remaining admissible pairs, we provide explicit constructions. For \((\alpha,\beta)=(6,3)\), the edge sets are given by \[(v_{22}; v_{11},v_{12},v_{13},v_{14}),\quad (v_{24}; v_{11},v_{12},v_{13},v_{14}),\] \[(v_{25}; v_{11},v_{12},v_{13},v_{14}),\quad (v_{26};v_{11},v_{12},v_{13},v_{14}),\] \[(v_{16}; v_{22}, v_{23}, v_{24},v_{25}),\quad (v_{21}; v_{11}, v_{12}, v_{14},v_{16}),\] \[(v_{21}, v_{13}, \underline{v_{23}},v_{12}; \underline{v_{11}}), \quad (v_{14},v_{23}, \underline{v_{15}}, v_{22}; \underline{v_{21}}),\] and \[(v_{16}, v_{26}, \underline{v_{15}},v_{24}; \underline{v_{25}}).\] For \((\alpha,\beta)=(8,1)\), the edge sets are given by \[(v_{21}; v_{11}, v_{12}, v_{13},v_{14}),\quad (v_{12}; v_{23}, v_{24}, v_{25},v_{26}),\] \[(v_{22}; v_{11}, v_{12}, v_{13},v_{14}),\quad (v_{23}; v_{11}, v_{13}, v_{14},v_{16}),\] \[(v_{24};v_{11}, v_{13}, v_{14},v_{16}),\quad (v_{26};v_{11}, v_{13}, v_{14},v_{15}),\] \[(v_{25}; v_{11}, v_{13}, v_{14}, v_{16}),\quad (v_{15}; v_{22}, v_{23}, v_{24},v_{25}),\] and \[(v_{15}, v_{21}, \underline{v_{16}}, v_{26}; \underline{v_{22}}).\] Thus, \(K_{6,6}\) admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=9\). ◻
Lemma 2.16. \(K_{2p,2q}\), where \(p,q>1\) are odd, admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=pq\).
Proof. Let \(p=2p_1+1\) and \(q=2q_1+1\) for some \(p_1,q_1\in\mathbb{N}\). We write \[K_{2p,2q}=(p_1-1)(q_1-1)K_{4,4} \oplus (p_1+q_1-2)K_{6,4} \oplus K_{6,6}.\] Since \(K_{6,4}\cong K_{4,6}\), by Lemma 2.6, \(K_{6,4}\) admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=6\), except when \(\beta=1\). Similarly, by Lemma 2.6, \(K_{4,4}\) admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=4\), except when \(\beta=1\). Further, by Lemma 2.15, \(K_{6,6}\) admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=9\). Hence, by Lemma 2.3 and Corollary 2.4 data-reference=”mypartition2.1″>[mypartition2.1], \(K_{2p,2q}\), for \(p,q>1\) odd, admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition whenever \(\alpha+\beta=pq\). ◻
Theorem 2.17. For \(m\geq4\) and \(n\geq2\), \(K_{m,n}\) admits a \(\{S_5^\alpha,Y_5^\beta\}\)-decomposition if and only if \(\alpha+\beta=\frac{mn}{4}\), \(mn\equiv0\pmod{4}\), and one of the following holds. Let \(p,q\in\mathbb{N}\).
1. \(m=4\), \(n\geq4\), and \(\beta\neq1\);
2. \(m=4p\), \(n=3\), and \(\beta\neq1\);
3. \(m=4p\), \(p\geq2\), and \(n\geq5\);
4. \(m=2p\), \(p>1\), \(n=2\), and
(i) \(\beta\) is even;
(ii) \(\beta\neq0\) if \(p\) is odd;
5. \(m=2p\), \(n=2q\), and \(p,q>1\) are odd.
Proof. Assume that \(K_{m,n}\) has an \((S_5^\alpha,Y_5^\beta)\)-decomposition. Then, from the edge-divisibility condition for the existence of an \((S_5^\alpha,Y_5^\beta)\)-decomposition of \(K_{m,n}\), we have \[\alpha+\beta=\frac{mn}{4}.\] Thus, any admissible pair must satisfy this arithmetic condition, and in particular \(mn\equiv0\pmod{4}\). Moreover, Lemmas 2.5, 2.8, and 2.12 restrict the admissible pairs to the five cases listed above. Hence, the stated conditions are necessary.
Conversely, let \((\alpha,\beta)\) be an admissible pair satisfying one of the above cases. Then the required decompositions of \(K_{m,n}\) follow from Lemmas 2.9, 2.6, 2.11, 2.14, and 2.16, respectively, corresponding to Cases (1)–(5). Hence, the sufficiency follows. ◻
In this section, we obtain necessary and sufficient conditions for the \(\{P_5^{\alpha},S_5^{\beta},Y_5^{\gamma}\}\)-decomposition of \(K_{m,n}\), where \(m\geq4\) and \(n\geq2\).
In the work of T. W. Shyu [17], Theorems 2.5–2.8 were established to address the \(\{P_k^{\alpha},S_k^{\beta}\}\)-decomposition of \(K_{m,n}\) for \(k\geq4\). Since, in the present study, we focus exclusively on the case \(k=5\), we restate and combine the relevant results into a single theorem accordingly, which is given in Theorem 3.1.
Theorem 3.1([17]).For \(m\geq4\) and \(n\geq2\), \(K_{m,n}\) admits a \(\{P_5^\alpha,S_5^\beta\}\)-decomposition if one of the following holds. Let \(p,q\in\mathbb{N}\).
1. \(m=4\), \(n\geq3\), and \(\alpha\neq1\);
2. \(m=4p\), \(n=3,4\), and \(\alpha\neq1\);
3. \(m=4p\), \(p\geq2\), and \(n\geq5\);
4. \(m=2p\), \(p\) is even, \(n=2\), and \(\beta\) is even;
5. \(m=2p\), \(n=2q\), \(p\geq3\), and \(q\geq7\) are odd.
Lemma 3.2([18]).For \(\alpha,\beta>0\), \(K_{2p,2}\), \(p\in\mathbb{N}\), admits a \(\{P_5^\alpha,S_5^\beta\}\)-decomposition if and only if \(p\geq2\) whenever \(\alpha+\beta=p\) and \(\beta\) is even.
Lemma 3.3([8])\(K_{6,6}\) admits a \(\{P_5^\alpha,S_5^\beta\}\)-decomposition whenever \(\alpha+\beta=9\).
Remark 3.4. We write \[K_{6,10}=K_{6,6}\oplus K_{6,4} \quad \text{and} \quad K_{10,10}=K_{6,10}\oplus K_{4,10}.\] By Lemma 3.3, \(K_{6,6}\) admits a \(\{P_5^\alpha,S_5^\beta\}\)-decomposition whenever \(\alpha+\beta=9\). By Theorem 3.1, \(K_{6,4}\) and \(K_{4,10}\) admit a \(\{P_5^\alpha,S_5^\beta\}\)-decomposition whenever \(\alpha+\beta=6\) and \(\alpha+\beta=10\), respectively, except when \(\alpha=1\). Hence, by Corollary 2.4, we have a \(\{P_5^\alpha,S_5^\beta\}\)-decomposition of \(K_{6,10}\) and \(K_{10,10}\) whenever \(\alpha+\beta=15\) and \(\alpha+\beta=25\), respectively.
Observation 3.5. Theorem 3.1, Lemmas 3.2 and 3.3, together with Remark 3.4, give necessary and sufficient conditions for the \(\{P_5^\alpha,S_5^\beta\}\)-decomposition of \(K_{m,n}\), where \(m\geq4\) and \(n\geq2\).
Theorem 3.6([3]).There exists a \(\{P_5^\alpha,Y_5^\beta\}\)-decomposition of \(K_{m,n}\) if and only if one of the following holds. Let \(p,q\in\mathbb{N}\).
1. \(m=2p\), \(p\) is even, \(n=2\), and \(\alpha\) is even;
2. \(m=2p\), \(p\geq3\) is odd, \(n=2\), and \(\alpha\) is odd;
3. \(m=4p\) and \(n\geq3\);
4. \(m=2p\) and \(n=2q\), where \(p,q\geq3\) are odd.
Remark 3.7. For any admissible triplet \((\alpha,\beta,\gamma)\) with at most two of the three entries in the triplet equal to \(0\), the proof follows directly from the results on \(\{H_1^\alpha,H_2^\beta\}\)-decomposition, where \(\{H_1,H_2\}\in\{P_5,S_5,Y_5\}\). These results are given in Observation 3.5, Theorem 3.6, and Theorem 2.17.
If \(Y_1,\ldots,Y_n\) are sets of ordered triplets of non-negative integers, then \[Y_1+\cdots+Y_n= \left\{ (a_1+\cdots+a_n,\, b_1+\cdots+b_n,\, c_1+\cdots+c_n) :\, (a_i,b_i,c_i)\in Y_i \text{ for } 1\le i\le n \right\}.\]
Lemma 3.8. Suppose that \(n,m\ge3\), \[\{(p,q,r)\in\mathbb{N}_0^3:p+q+r=n,\ (p,r)\notin\{(1,0),(1,1),(0,1)\}\}\subseteq Y_1\] and \[\{(a,b,c)\in\mathbb{N}_0^3:a+b+c=m,\ (a,c)\notin\{(1,0),(1,1),(0,1)\}\}\subseteq Y_2.\] Define \[G_3:=\{(s,t,u)\in\mathbb{N}_0^3:s+t+u=n+m,\ (s,u)\notin\{(1,0),(1,1),(0,1)\}\}.\] Then \(G_3\subseteq Y_1+Y_2\).
Proof. It is easy to see that \((s,t,u)\notin Y_1+Y_2\) whenever \[(s,u)\in\{(1,0),(1,1),(0,1)\}.\] To prove the claim, it suffices to show that \[\label{eq2} \forall (s,t,u)\in G_3,\ \exists\ p_1,q_1,r_1,a_1,b_1,c_1\in\mathbb{N}_0: \begin{cases} (s,t,u)=(p_1+a_1,\ q_1+b_1,\ r_1+c_1),\\ p_1+q_1+r_1=n,\quad a_1+b_1+c_1=m,\\ (p_1,r_1)\notin\{(1,0),(1,1),(0,1)\},\\ (a_1,c_1)\notin\{(1,0),(1,1),(0,1)\}. \end{cases} \tag{2}\]
Note that \(p_1,q_1,r_1\leq n\) and \(a_1,b_1,c_1\leq m\). The elements \(p_1,q_1,r_1,a_1,b_1,c_1\) satisfying the conditions given in (2), for \(m,n\geq3\), can be obtained in the following seven cases.
Case 1. \(u=0\), \(s=n+1\), and \(t=m-1\).
Choose \[(p_1,q_1,r_1)=(n-1,1,0) \quad \text{and} \quad (a_1,b_1,c_1)=(2,m-2,0).\]
Case 2. \(u=1\), \(s=n+1\), and \(t=m-2\).
Choose \[(p_1,q_1,r_1)=(n-1,0,1) \quad \text{and} \quad (a_1,b_1,c_1)=(2,m-2,0).\]
Case 3. \(u=1\) and \(s\leq n\).
Choose \[(p_1,q_1,r_1)=(s,n-1-s,1) \quad \text{and} \quad (a_1,b_1,c_1)=(0,m,0).\] Since \(u=1\), we have \(s\neq0,1\).
Case 4. \(s=0\), \(u=m+1\), and \(t=n-1\).
Choose \[(p_1,q_1,r_1)=(0,n-2,2) \quad \text{and} \quad (a_1,b_1,c_1)=(0,1,m-1).\]
Case 5. \(s=1\), \(u=m+1\), and \(t=n-2\).
Choose \[(p_1,q_1,r_1)=(1,n-3,2) \quad \text{and} \quad (a_1,b_1,c_1)=(0,1,m-1).\]
Case 6. \(s=1\) and \(u\leq m\).
Choose \[(p_1,q_1,r_1)=(0,n,0) \quad \text{and} \quad (a_1,b_1,c_1)=(1,m-1-u,u).\]
Case 7. Any \((s,t,u)\) that does not fall under Cases 1–6.
Let \[c_1=\min(u,m),\quad p_1=\min(s,n),\quad a_1=s-p_1,\] \[b_1=m-(a_1+c_1),\quad q_1=t-b_1,\quad r_1=u-c_1.\] It is clear that \(a_1+b_1+c_1=m\), \(a_1,r_1\geq0\), \(b_1\leq m\), \(0\leq c_1\leq m\), and \(0\leq p_1\leq n\).
Subclaim 1. \(a_1\leq m\).
If \(p_1=\min(s,n)=s\), then \(a_1=s-p_1=0\leq m\). If \(p_1=n\), then \(a_1\leq m\) because \[s+t+u=m+n \implies s\leq m+n \iff s-n\leq m.\]
Subclaim 2. \(b_1\geq0\).
It is enough to show that \[m-s\geq \min(u,m)-\min(s,n). \label{3}\] If \(\min(u,m)=m\), then \(\min(s,n)=s\) because \[s+t+u=n+m \implies s+t\leq n \implies s\leq n. \] The inequality becomes equality in this case. When \(\min(u,m)=u\) and \(\min(s,n)=n\), since \[s+t+u=n+m \implies s+u\leq n+m \iff u-n\leq m-s,\] (3) holds. Also, for \(\min(u,m)=u\) and \(\min(s,n)=s\), \[m\geq u \iff m-s\geq u-s.\] Therefore, (3) holds.
Subclaim 3. \(0\leq q_1\leq n\).
To prove \(q_1\geq0\), it is enough to show that \[t+s-m\geq \min(s,n)-\min(u,m). \label{2} \tag{4}\] As in Subclaim 2, if \(\min(u,m)=m\), then \(\min(s,n)=s\). Therefore, \[t\geq0 \iff t+s-m\geq s-m,\] and (4) holds. When \(\min(u,m)=u\) and \(\min(s,n)=n\), the inequality becomes equality because \(s+t+u=n+m\). Also, for \(\min(u,m)=u\) and \(\min(s,n)=s\), since \(n\geq s\), we have \[m+n\geq m+s \implies s+t+u\geq m+s,\] because \(s+t+u=n+m\). Therefore, (4) holds.
Now, to prove \(q_1\leq n\), we use \[s+t+u=n+m \implies t-m+s+u=n\] which implies \[t-m+s+\min(u,m)\leq n\] and hence \[t-m+s+\min(u,m)-\min(s,n)\leq n.\]
Subclaim 4. \(r_1\leq n\).
If \(c_1=\min(u,m)=u\), then \(r_1=u-c_1=0\leq n\). If \(c_1=m\), then \(r_1\leq n\) because \[s+t+u=m+n \implies u\leq m+n \iff u-m\leq n.\]
Subclaim 5. \(p_1+q_1+r_1=n\).
Indeed, \[p_1+q_1+r_1 =p_1+t-b_1+u-c_1 =p_1+t-m+a_1+c_1+u-c_1\] \[=p_1+t-m+s-p_1+u =t-m+s+u=n.\] ◻
Corollary 3.9. Suppose that \(n,m\ge3\), \[\{(p,q,r)\in\mathbb{N}_0^3:p+q+r=n,\ (p,r)\notin\{(1,0),(1,1),(0,1)\}\}\subseteq Y_3\] and \[\{(a,b,c)\in\mathbb{N}_0^3:a+b+c=m,\ (a,c)\notin\{(1,0),(0,1)\}\}\subseteq Y_4.\] Define \[G_4:=\{(s,t,u)\in\mathbb{N}_0^3:s+t+u=n+m,\ (s,u)\notin\{(1,0),(0,1)\}\}.\] Then \(G_4\subseteq Y_3+Y_4\).
Proof. It is easy to see that if \((s,u)\in\{(1,0),(0,1)\}\), then \((s,t,u)\notin Y_3+Y_4\). When \[(s,t,u)=(1,m+n-2,1),\] take \[(p_1,q_1,r_1)=(0,n,0) \quad \text{and} \quad (a_1,b_1,c_1)=(1,m-2,1).\] For the remaining \((s,t,u)\in G_4\), the elements \(p_1,q_1,r_1,a_1,b_1,c_1\) given in Lemma 3.8 suffice. ◻
Corollary 3.10. Suppose that \[\{(p,q,r)\in\mathbb{N}_0^3:p+q+r=n\}\subseteq Y_5\] and \[\{(a,b,c)\in\mathbb{N}_0^3:a+b+c=m\}\subseteq Y_6.\] Then \[\{(s,t,u)\in\mathbb{N}_0^3:s+t+u=n+m\}\subseteq Y_5+Y_6.\]
Proof. For any \((s,t,u)\) satisfying \(s+t+u=n+m\), the elements \(p_1,q_1,r_1,a_1,b_1,c_1\) constructed in Case 7 of Lemma 3.8 suffice. ◻
Lemma 3.11. There is no \(\{P_5^{\alpha},S_5^{\beta},Y_5^{\gamma}\}\)-decomposition of \(K_{2p,2}\), \(p>1\), whenever \(\alpha+\beta+\gamma=p\), \(\alpha,\beta,\gamma>0\), and \(\gamma\) is odd.
Proof. The vertices \(v_{2j}\), \(j\in\{1,2\}\), must serve as centers of the \(Y_5\) in a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition of \(K_{2p,2}\). If \(\gamma\) is odd, then each \(v_{2j}\) has odd degree in \(K_{2p,2}-\gamma Y_5\). However, to decompose \(K_{2p,2}-\gamma Y_5\) into \(\alpha P_5\) and \(\beta S_5\), where \(\alpha+\beta+\gamma=p\), each \(v_{2j}\) must have even degree, since it must be the center of an \(S_5\) and cannot serve as a pendant vertex of a \(P_5\). This is a contradiction, and hence the result follows. ◻
Remark 3.12.
There is no admissible triplet \((\alpha,\beta,\gamma)\) in \(K_{4,2}\) with \(\alpha,\beta,\gamma>0\).
The triplet \((1,1,1)\) is the only admissible triplet in \(K_{6,2}\) with \(\alpha,\beta,\gamma>0\), and \(K_{6,2}\) does not admit a \(\{P_5^1,S_5^1,Y_5^1\}\)-decomposition by Lemma 3.11.
In \(K_{8,2}\), the edge set for the admissible triplet \((1,1,2)\) is given by \[(v_{18},v_{21},v_{17},v_{22},v_{12}),\] \[(v_{21};v_{11},v_{12},v_{13},v_{14}),\] \[(v_{21},v_{15},\underline{v_{22}},v_{14};\underline{v_{13}})\] and \[(v_{21},v_{16},\underline{v_{22}},v_{18};\underline{v_{11}}).\] For all other admissible triplets with \(\alpha,\beta,\gamma>0\), \(K_{8,2}\) does not admit a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition by Lemma 3.11.
Lemma 3.13. \(K_{2p,2}\), \(p>1\), admits a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition whenever \(\alpha+\beta+\gamma=p\) and one of the following holds:
(i) \(\gamma=0\) and \(\beta\) is even;
(ii) \(\beta=0\) and \(\gamma\) is even;
(iii) \(\alpha=0\), \(\gamma\) is even, and \(\gamma\ne0\) if \(p\) is odd;
(iv) \(\alpha,\beta,\gamma>0\) and \(\gamma\) is even.
Proof. For (i), (ii), and (iii), Remark 3.7 gives the required proof.
(iv) Case 1. \(p\) is odd.
Let \(p=2p_1+1\) for some \(p_1\in\mathbb{N}\). Then \[K_{2p,2}=K_{2(2p_1+1),2}=K_{6,2}\oplus(p_1-1)K_{4,2}.\]
Subcase 1. \(\beta\) is even.
In this case, take \(K_{6,2}=(1,0,2)\). Also, in the subgraph \((p_1-1)K_{4,2}\), for \(\frac{\gamma-2}{2}K_{4,2}\), take \(K_{4,2}=(0,0,2)\); for \(\frac{\beta}{2}K_{4,2}\), take \(K_{4,2}=(0,2,0)\); and for \(\frac{\alpha-1}{2}K_{4,2}\), take \(K_{4,2}=(2,0,0)\), so that \[\frac{\gamma-2}{2}+\frac{\beta}{2}+\frac{\alpha-1}{2}=p_1-1,\] because \(\alpha+\beta+\gamma=p=2p_1+1\).
Subcase 2. \(\beta\) is odd.
Take \(K_{6,2}=(0,1,2)\). In the subgraph \((p_1-1)K_{4,2}\), for \(\frac{\gamma-2}{2}K_{4,2}\), take \(K_{4,2}=(0,0,2)\); for \(\frac{\beta-1}{2}K_{4,2}\), take \(K_{4,2}=(0,2,0)\); and for \(\frac{\alpha}{2}K_{4,2}\), take \(K_{4,2}=(2,0,0)\), so that \[\frac{\gamma-2}{2}+\frac{\beta-1}{2}+\frac{\alpha}{2}=p_1-1.\]
Case 2. \(p\) is even.
Let \(p=2p_1\) for some \(p_1\in\mathbb{N}\). Then \[K_{2p,2}=K_{4p_1,2}=K_{8,2}\oplus(p_1-2)K_{4,2}\] for \(p_1\geq2\). When \(p_1=1\), we have \(K_{4p_1,2}=K_{4,2}\).
Subcase 1. \(\beta\) is even.
Take \(K_{8,2}=(0,2,2)\). In the subgraph \((p_1-2)K_{4,2}\), for \(\frac{\gamma-2}{2}K_{4,2}\), take \(K_{4,2}=(0,0,2)\); for \(\frac{\beta-2}{2}K_{4,2}\), take \(K_{4,2}=(0,2,0)\); and for \(\frac{\alpha}{2}K_{4,2}\), take \(K_{4,2}=(2,0,0)\), so that \[\frac{\gamma-2}{2}+\frac{\beta-2}{2}+\frac{\alpha}{2}=p_1-2.\]
Subcase 2. \(\beta\) is odd.
Take \(K_{8,2}=(1,1,2)\). In the subgraph \((p_1-2)K_{4,2}\), for \(\frac{\gamma-2}{2}K_{4,2}\), take \(K_{4,2}=(0,0,2)\); for \(\frac{\beta-1}{2}K_{4,2}\), take \(K_{4,2}=(0,2,0)\); and for \(\frac{\alpha-1}{2}K_{4,2}\), take \(K_{4,2}=(2,0,0)\), so that \[\frac{\gamma-2}{2}+\frac{\beta-1}{2}+\frac{\alpha-1}{2}=p_1-2.\] ◻
<Lemma 3.14.
There is no \(\{P_5^{1},S_5^{3p-2},Y_5^{1}\}\)-decomposition of \(K_{4p,3}\) whenever \(\alpha+\beta+\gamma=3p\).Proof. The vertices \(v_{2j}\), \(1\le j\le3\), must serve as centers of the \(S_5\) in a \(\{P_5^1,S_5^{3p-2},Y_5^1\}\)-decomposition of \(K_{4p,3}\). Each vertex \(v_{2j}\) can be the center of at most \(p\) stars. Hence, at least one of the vertices \(v_{2j}\), say \(v_{21}\), must be the center of \(p\) copies of \(S_5\). Removing these \(p\) stars, we obtain \[K_{4p,3}-pS_5\cong K_{4p,2},\] where each removed \(S_5\) has center at \(v_{21}\). Thus, the problem reduces to determining whether \(K_{4p,2}\) admits a \(\{P_5^1,S_5^{2p-2},Y_5^1\}\)-decomposition. By Lemma 3.11, no such decomposition exists, and hence the result follows. ◻
Remark 3.15. The only admissible triplet \((\alpha,\beta,\gamma)\) in \(K_{4,3}\) with \(\alpha,\beta,\gamma>0\) is \((1,1,1)\), and \(K_{4,3}\) does not admit a \(\{P_5^1,S_5^1,Y_5^1\}\)-decomposition by Lemma 3.14.
Lemma 3.16. \(K_{4p,3}\) admits a \(\{P_5^{\alpha},S_5^{\beta},Y_5^{\gamma}\}\)-decomposition whenever \(\alpha+\beta+\gamma=3p\) and \[(\alpha,\gamma)\notin\{(0,1),(1,1),(1,0)\}.\]
Proof. We write \[K_{4p,3}=pK_{4,3}.\] By Remarks 3.7 and 3.15, \(K_{4,3}\) admits a \(\{P_5^{\alpha},S_5^{\beta},Y_5^{\gamma}\}\)-decomposition whenever \(\alpha+\beta+\gamma=3\) and \[(\alpha,\gamma)\notin\{(0,1),(1,1),(1,0)\}.\] Hence, by Lemma 3.8, \(K_{4p,3}\) admits a \(\{P_5^{\alpha},S_5^{\beta},Y_5^{\gamma}\}\)-decomposition whenever \(\alpha+\beta+\gamma=3p\) and \[(\alpha,\gamma)\notin\{(0,1),(1,1),(1,0)\}.\] ◻
Lemma 3.17. \(K_{4,n}\), \(n\ge4\), admits a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition whenever \(\alpha+\beta+\gamma=n\), \[(\alpha,\gamma)\notin\{(0,1),(1,0)\},\] and, in addition, \[(\alpha,\beta,\gamma)\ne(1,2,1)\] when \(n=4\).
Proof. If one or two of \(\alpha,\beta,\gamma\) are zero, the result follows from Remark 3.7. Hence, assume that \(\alpha,\beta,\gamma>0\). We write \[K_{4,i}=S_5\oplus K_{4,i-1}.\] This recursion starts from the base case \(K_{4,3}\), which admits a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition whenever \(\alpha+\beta+\gamma=3\) and \[(\alpha,\gamma)\notin\{(0,1),(1,1),(1,0)\}\] by Remarks 3.7 and 3.15. Given an admissible triplet \((\alpha,\beta,\gamma)\) in \(K_{4,i}\), consider the triplet \((\alpha,\beta-1,\gamma)\) in \(K_{4,i-1}\). By this recursive construction, we obtain a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition for all \(\alpha,\beta,\gamma>0\), except when \[(\alpha,\beta,\gamma)=(1,n-2,1).\] For \(i=4\), a \(\{P_5^1,S_5^2,Y_5^1\}\)-decomposition does not exist, since \[K_{4,4}-2S_5\cong K_{4,2},\] and \(K_{4,2}\) cannot be decomposed into \(P_5\) and \(Y_5\) by Theorem 3.6. For \(i=5\), the edge set for the admissible triplet \((1,3,1)\) is given by \[(v_{11},v_{21},v_{12},v_{22},v_{13}),\] \[(v_{11};v_{22},v_{23},v_{24},v_{25}), \quad (v_{13};v_{21},v_{23},v_{24},v_{25}),\] \[(v_{14};v_{21},v_{22},v_{24},v_{25})\] and \[(v_{14},v_{23},\underline{v_{12}},v_{25};\underline{v_{24}}).\] For \(n\ge6\), we obtain \[(1,n-2,1)=(0,1,0)+(1,n-3,1),\] with the base case \((1,3,1)\) arising from \(K_{4,5}\). ◻
Lemma 3.18. \(K_{4p,n}\), \(p\ge2\) and \(n\ge5\), admits a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition whenever \(\alpha+\beta+\gamma=pn\).
Proof. Let \(n=4q+r\), where \(q\in\mathbb{N}\) and \(r\in\{0,1,2,3\}\).
Case 1. \(r=0\).
If \(q=1\), then \(n=4\). Hence, assume \(q\ge2\). We write \[K_{4p,4q}=pK_{4,8}\oplus p(q-2)K_{4,4}.\]
Case 2. \(r\in\{1,2,3\}\).
We write \[K_{4p,4q+r}=p(q-1)K_{4,4}\oplus pK_{4,i},\] where \(i=5\) if \(r=1\), \(i=6\) if \(r=2\), and \(i=7\) if \(r=3\).
By Lemma 3.17, \(K_{4,4}\) admits a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition whenever \(\alpha+\beta+\gamma=4\) and \[(\alpha,\gamma)\notin\{(0,1),(1,1),(1,0)\}.\] Further, for \(i\in\{5,6,7,8\}\), \(K_{4,i}\) admits a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition whenever \(\alpha+\beta+\gamma=i\) and \[(\alpha,\gamma)\notin\{(0,1),(1,0)\}.\] Hence, by Corollary 3.9, we obtain a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition of \(K_{4p,n}\) whenever \(\alpha+\beta+\gamma=pn\) and \[(\alpha,\gamma)\notin\{(0,1),(1,0)\}.\] Finally, for \((\alpha,\gamma)\in\{(0,1),(1,0)\}\), the required decomposition exists by Remark 3.7. ◻
Lemma 3.19. \(K_{6,6}\) admits a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition whenever \(\alpha+\beta+\gamma=9\).
Proof. We write \[K_{6,6}=K_{4,6}\oplus K_{2,6}.\] Except for the admissible triplet \((1,7,1)\), this partition yields a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition for all admissible triplets, as listed in Table 1. For \((1,7,1)\), the edge set is given by \[(v_{24},v_{13},v_{25},v_{14},v_{26}),\] \[(v_{21};v_{11},v_{12},v_{13},v_{14}), \quad (v_{22};v_{11},v_{12},v_{13},v_{14}),\] \[(v_{23};v_{11},v_{12},v_{13},v_{14}), \quad (v_{24};v_{11},v_{12},v_{14},v_{15}),\] \[(v_{25};v_{11},v_{12},v_{15},v_{16}), \quad (v_{26};v_{11},v_{12},v_{13},v_{15}),\] \[(v_{16};v_{21},v_{22},v_{24},v_{26})\] and \[(v_{16},v_{23},\underline{v_{15}},v_{22};\underline{v_{21}}).\] ◻
Lemma 3.20. \(K_{2p,2q}\), where \(p,q>1\) are odd, admits a \(\{P_5^{\alpha},S_5^{\beta},Y_5^{\gamma}\}\)-decomposition whenever \(\alpha+\beta+\gamma=pq\).
Proof. Let \(p=2p_1+1\) and \(q=2q_1+1\) for some \(p_1,q_1\in\mathbb{N}\). We write \[K_{2p,2q} = (p_1-1)(q_1-1)K_{4,4} \oplus (p_1+q_1-2)K_{6,4} \oplus K_{6,6}.\] Since \(K_{6,4}\cong K_{4,6}\), by Lemma 3.17, \(K_{6,4}\) admits a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition whenever \(\alpha+\beta+\gamma=6\) and \[(\alpha,\gamma)\notin\{(0,1),(1,0)\}.\] Similarly, by Lemma 3.17, \(K_{4,4}\) admits a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition whenever \(\alpha+\beta+\gamma=4\) and \[(\alpha,\gamma)\notin\{(0,1),(1,1),(1,0)\}.\] Further, by Lemma 3.19, \(K_{6,6}\) admits a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition whenever \(\alpha+\beta+\gamma=9\). Hence, by Lemma 3.8 and Corollary 3.9, we obtain a \(\{P_5^{\alpha},S_5^{\beta},Y_5^{\gamma}\}\)-decomposition of \(K_{2p,2q}\) whenever \(\alpha+\beta+\gamma=pq\) and \[(\alpha,\gamma)\notin\{(0,1),(1,0)\}.\] Finally, for \((\alpha,\gamma)\in\{(0,1),(1,0)\}\), the required decomposition exists by Remark 3.7. ◻
Theorem 3.21. For \(m\geq4\) and \(n\geq2\), \(K_{m,n}\) has a \(\{P_5^{\alpha},S_5^{\beta},Y_5^{\gamma}\}\)-decomposition if and only if \(\alpha+\beta+\gamma=\frac{mn}{4}\), \(mn\equiv0\pmod{4}\), and one of the following holds. Let \(p,q\in\mathbb{N}\).
1. \(m=2p\), \(p\geq2\), \(n=2\), and
(i) \(\gamma=0\) and \(\beta\) is even;
(ii) \(\beta=0\) and \(\gamma\) is even;
(iii) \(\alpha=0\), \(\gamma\) is even, and \(\gamma\ne0\) if \(p\) is odd;
(iv) \(\alpha,\beta,\gamma>0\) and \(\gamma\) is even.
2. \(m=4p\), \(n=3\), and \[(\alpha,\gamma)\notin\{(0,1),(1,1),(1,0)\}.\]
3. \(m=4\), \(n\geq4\), and
(i) \((\alpha,\gamma)\notin\{(0,1),(1,0)\}\);
(ii) \((\alpha,\beta,\gamma)\neq(1,2,1)\) when \(n=4\).
4. \(m=4p\), \(p\geq2\), and \(n\geq5\).
5. \(m=2p\), \(n=2q\), and \(p,q>1\) are odd.
Proof. Assume that \(K_{m,n}\) has a \(\{P_5^{\alpha},S_5^{\beta},Y_5^{\gamma}\}\)-decomposition. Then, from the edge-divisibility condition for the existence of a \(\{P_5^{\alpha},S_5^{\beta},Y_5^{\gamma}\}\)-decomposition of \(K_{m,n}\), we have \[\alpha+\beta+\gamma=\frac{mn}{4}.\] Thus, any admissible triplet must satisfy this arithmetic condition, and in particular \(mn\equiv0\pmod{4}\). Moreover, Lemmas 3.11, 3.13, 3.14, and 3.17 restrict the admissible triplets to the five cases listed above. Hence, the stated conditions are necessary.
Conversely, let \((\alpha,\beta,\gamma)\) be an admissible triplet satisfying one of the above cases. Then the required decompositions of \(K_{m,n}\) follow from Lemmas 3.13, 3.16, 3.17, 3.18, and 3.20, corresponding respectively to Cases (1)–(5). Hence, the sufficiency follows. ◻
In this section, we obtain necessary and sufficient conditions for the \(\{P_5^{\alpha},S_5^{\beta},Y_5^{\gamma}\}\)-decomposition of \(K_n\), where \(n\geq8\). We recall some results required for our main theorem.
Lemma 4.1([8]).There exists a \(\{P_5^\alpha,S_5^\beta\}\)-decomposition of \(K_n\) for \(n=8,9\) whenever \(\alpha+\beta=7\) and \(\alpha+\beta=9\), respectively.
Theorem 4.2 ([3]).For non-negative integers \(\alpha\), \(\beta\), and \(n\geq8\), \[K_n=\alpha P_5\oplus \beta Y_5\] if and only if \[4(\alpha+\beta)=\binom{n}{2}.\]
Note 4.3. Figure 1 illustrates two graphs with \(8\) edges that can be decomposed into different combinations of \(P_5\), \(S_5\), and \(Y_5\), namely \(2S_5\), \(2Y_5\), \(1S_5\oplus1Y_5\), and \(1P_5\oplus1Y_5\).
| Graph | \(2S_5\) | \(2Y_5\) | \(1S_5\oplus 1Y_5\) | \(1P_5\oplus 1Y_5\) |
| \(G_1\) | \(\{3;1,2,4,5\}\), \(\{1;2,6,7,8\}\) | \(\{8,1,\underline{3},5;\underline{4}\}\), \(\{3,2,\underline{1},7;\underline{6}\}\) | \(\{1;3,6,7,8\}\), \(\{1,2,\underline{3},5;\underline{4}\}\) | \(\{8,1,2,3,4\}\), \(\{5,3,\underline{1},6;\underline{7}\}\) |
| \(G_2\) | \(\{3;1,2,4,5\}\), \(\{4;1,2,5,6\}\) | \(\{6,4,\underline{3},1;\underline{2}\}\), \(\{3,5,\underline{4},1;\underline{2}\}\) | \(\{4;1,2,3,6\}\), \(\{4,5,\underline{3},1;\underline{2}\}\) | \(\{2,4,5,3,1\}\), \(\{2,3,\underline{4},1;\underline{6}\}\) |
Definition 4.4([4]).A connected graph \(G\) with \(8\) edges is called a \(PY5\) graph if \[G=2P_5=2Y_5=P_5\oplus Y_5.\]
Note 4.5. Here we recall two \(PY5\) graphs from [4] that can also be decomposed into \(1P_5\oplus1S_5\).
| Graph | \(2P_5\) | \(2Y_5\) | \(1P_5\oplus 1Y_5\) | \(1P_5\oplus 1S_5\) |
| \(T_1\) | \(\{5,6,1,2,3\}\), \(\{6,2,5,4,3\}\) | \(\{4,5,\underline{6},1;\underline{2}\}\), \(\{4,3,\underline{2},1;\underline{5}\}\) | \(\{1,2,5,4,3\}\), \(\{3,2,\underline{6},5;\underline{1}\}\) | \(\{1,6,5,4,3\}\), \(\{2;1,3,5,6\}\) |
| \(T_2\) | \(\{6,1,5,2,4\}\), \(\{1,2,3,4,5\}\) | \(\{1,5,\underline{4},2;\underline{3}\}\), \(\{6,1,\underline{2},5;\underline{3}\}\) | \(\{6,1,5,4,2\}\), \(\{4,3,\underline{2},5;\underline{1}\}\) | \(\{6,1,5,4,3\}\), \(\{2;1,3,4,5\}\) |
Lemma 4.6. For \(\alpha\geq0\) and \(\beta,\gamma>0\), \(K_8\) admits a \(\{P_5^{\alpha},S_5^{\beta},Y_5^{\gamma}\}\)-decomposition whenever \(\alpha+\beta+\gamma=7\).
Proof. Since \(|E(K_8)|=28\) and each tree of order five has four edges, any such decomposition must consist of seven trees. The construction proceeds by partitioning the edge set into three edge-disjoint subgraphs \(H_1\), \(H_2\), and \(H_3\), together with a tree of order five, where \(H_i\in\{G_1,G_2,T_1,T_2\}\), such that the subgraphs \(G_1\) and \(G_2\) are the graphs given in Note 4.3, and \(T_1\) and \(T_2\) are the graphs given in Note 4.5. Depending on the degree structure of \(G_1\), \(G_2\), \(T_1\), and \(T_2\), each can be further decomposed into two trees of order five of type \(P_5\), \(S_5\), or \(Y_5\). By combining these decompositions appropriately, we obtain the required admissible triplets \((\alpha,\beta,\gamma)\).
First write \[K_8=1G_1\oplus2G_2\oplus1S_5,\] where the edge sets of the subgraphs in the given order are \[\{v_3v_6,v_3v_7,v_3v_8,v_3v_5,v_4v_3,v_4v_5,v_4v_2,v_4v_1\},\] \[\{v_2v_1,v_2v_3,v_2v_5,v_2v_8,v_1v_3,v_1v_5,v_1v_8,v_1v_6\},\] \[\{v_8v_4,v_8v_5,v_8v_6,v_8v_7,v_6v_2,v_6v_4,v_6v_5,v_6v_7\},\] and \[\{v_7;v_1,v_2,v_4,v_5\}.\] This decomposition yields admissible triplets \((\alpha,\beta,\gamma)\) for \(\alpha=0,1\), as listed in Table 2.
Next write \[K_8=1T_2\oplus2G_2\oplus1P_5,\] where the corresponding edge sets are \[\{v_6v_1,v_6v_5,v_6v_2,v_6v_7,v_8v_7,v_7v_2,v_2v_5,v_5v_1\},\] \[\{v_2v_1,v_2v_3,v_2v_4,v_2v_8,v_1v_3,v_1v_4,v_1v_7,v_1v_8\},\] \[\{v_4v_3,v_4v_5,v_4v_6,v_4v_8,v_3v_5,v_3v_6,v_3v_7,v_3v_8\},\] and \[\{v_4,v_7,v_5,v_8,v_6\}.\] This construction gives the required decompositions for \(\alpha=2,3,4\), as listed in Table 2. Finally, for \((\alpha,\beta,\gamma)=(5,1,1)\), the edge sets are \[\{v_8,v_6,v_1,v_2,v_3\},\quad \{v_5,v_2,v_8,v_1,v_3\},\] \[\{v_2,v_6,v_4,v_8,v_5\},\quad \{v_1,v_5,v_6,v_7,v_8\},\] \[\{v_7,v_3,v_5,v_4,v_1\},\quad \{v_7;v_1,v_2,v_4,v_5\},\] and \[\{v_2,v_4,\underline{v_3},v_8;\underline{v_6}\}.\]
A direct verification shows that the listed subgraphs are pairwise edge-disjoint, and their union equals \(E(K_8)\). Thus, \(K_8\) admits a \(\{P_5^{\alpha},S_5^{\beta},Y_5^{\gamma}\}\)-decomposition for \(\alpha\ge0\) and \(\beta,\gamma>0\) whenever \(\alpha+\beta+\gamma=7\). ◻
Lemma 4.7. For \(\alpha\geq0\) and \(\beta,\gamma>0\), \(K_9\) admits a \(\{P_5^{\alpha},S_5^{\beta},Y_5^{\gamma}\}\)-decomposition whenever \(\alpha+\beta+\gamma=9\).
Proof. Since \(|E(K_9)|=36\) and each tree of order five has four edges, any such decomposition must consist of nine trees. The construction proceeds similarly by partitioning the edge set into four edge-disjoint subgraphs \(H_1\), \(H_2\), \(H_3\), and \(H_4\), together with a tree of order five, where \(H_i\in\{G_1,G_2,T_1,T_2\}\). Each of these subgraphs can be further decomposed into two trees of order five of type \(P_5\), \(S_5\), or \(Y_5\), depending on its degree structure. By combining these decompositions appropriately, we obtain the required admissible triplets \((\alpha,\beta,\gamma)\).
First write \[K_9=1G_1\oplus3G_2\oplus1S_5,\] where the edge sets of the subgraphs in the given order are \[\{v_4v_1,v_4v_2,v_4v_3,v_4v_5,v_3v_5,v_3v_6,v_3v_7,v_3v_9\},\] \[\{v_2v_1,v_2v_3,v_2v_5,v_2v_9,v_1v_3,v_1v_5,v_1v_9,v_1v_6\},\] \[\{v_6v_2,v_6v_4,v_6v_7,v_6v_5,v_7v_1,v_7v_2,v_7v_4,v_7v_5\},\] \[\{v_8v_5,v_8v_6,v_8v_7,v_8v_9,v_9v_4,v_9v_5,v_9v_6,v_9v_7\},\] and \[\{v_8;v_1,v_2,v_3,v_4\}.\] This decomposition yields admissible triplets \((\alpha,\beta,\gamma)\) for \(\alpha=0,1\), as listed in Table 3.
Next write \[K_9=1T_1\oplus3G_2\oplus1P_5,\] where the corresponding edge sets are \[\{v_6v_1,v_6v_2,v_6v_3,v_6v_7,v_3v_7,v_7v_1,v_1v_5,v_5v_2\},\] \[\{v_2v_1,v_2v_3,v_2v_4,v_2v_9,v_1v_3,v_1v_4,v_1v_8,v_1v_9\},\] \[\{v_3v_4,v_3v_5,v_3v_8,v_3v_9,v_4v_5,v_4v_7,v_4v_8,v_4v_9\},\] \[\{v_9v_5,v_9v_6,v_9v_7,v_9v_8,v_8v_2,v_8v_5,v_8v_6,v_8v_7\},\] and \[\{v_4,v_6,v_5,v_7,v_2\}.\] This construction yields the required decompositions for \(\alpha=2,3,4,5\), except \((5,3,1)\), as listed in Table 3.
For \((\alpha,\beta,\gamma)=(5,3,1)\), the edge sets are \[\{v_3,v_2,v_1,v_6,v_7\},\quad \{v_5,v_2,v_9,v_1,v_3\},\] \[\{v_1,v_7,v_2,v_6,v_5\},\quad \{v_1,v_5,v_7,v_4,v_6\},\] \[\{v_6,v_9,v_7,v_8,v_5\},\] \[\{v_8;v_1,v_2,v_3,v_4\}, \quad \{v_3;v_5,v_6,v_7,v_9\},\] \[\{v_4;v_1,v_2,v_3,v_5\}\] and \[\{v_6,v_8,\underline{v_9},v_5;\underline{v_4}\}.\] Finally, by rearranging the edges of the three copies of \(G_2\) in the decomposition \[K_9=1G_1\oplus3G_2\oplus1S_5,\] we obtain six copies of \(P_5\): \[\{v_3,v_2,v_1,v_6,v_7\},\quad \{v_5,v_2,v_9,v_1,v_3\},\] \[\{v_9,v_6,v_5,v_1,v_7\},\quad \{v_4,v_6,v_2,v_7,v_5\},\] \[\{v_5,v_8,v_9,v_4,v_7\}\] and \[\{v_6,v_8,v_7,v_9,v_5\}.\] This gives the required decompositions for \(\alpha=6,7\), as listed in Table 3.
A direct verification shows that the listed subgraphs are pairwise edge-disjoint, and their union equals \(E(K_9)\). Thus, \(K_9\) admits a \(\{P_5^{\alpha},S_5^{\beta},Y_5^{\gamma}\}\)-decomposition for \(\alpha\ge0\) and \(\beta,\gamma>0\) whenever \(\alpha+\beta+\gamma=9\). ◻
Lemma 4.8. \(K_n\) admits a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition whenever \(n=4p\) or \(4p+1\), where \(p\) is even and \[\alpha+\beta+\gamma=\frac{n(n-1)}{8}.\]
Proof. We prove this by induction on \(p\).
Case 1. \(n=4p\).
When \(p=2\), \(K_8\) admits a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition whenever \(\alpha+\beta+\gamma=7\) by Lemmas 4.1, 4.6, and Theorem 4.2. Assume that, for some even \(p\geq4\), \(K_{4(p-2)}\) admits the required decomposition. Since \[V(K_{4p})=\{v_i:1\leq i\leq4p\},\] let \[V_1=\{v_i:1\leq i\leq8\} \quad \text{and} \quad V_2=\{v_i:9\leq i\leq4p\}.\] Then the subgraph induced by \(V_1\) is \(K_8\). Also, the subgraph induced by \(V_2\) is \(K_{4(p-2)}\), which admits a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition whenever \[\alpha+\beta+\gamma=\frac{(p-2)(4p-9)}{2}\] by the induction hypothesis. The edges between the vertices in \(V_1\) and \(V_2\) give rise to \(K_{8,4(p-2)}\), which admits a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition whenever \[\alpha+\beta+\gamma=8(p-2)\] by Case 4 of Theorem 3.21. Therefore, for \(p\geq4\), we write \[K_{4p}=K_8\oplus K_{4(p-2)}\oplus K_{8,4(p-2)}.\] Now, by Corollary 3.10, \(K_{4p}\) admits a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition whenever \[\alpha+\beta+\gamma=\frac{p(4p-1)}{2}.\]
Case 2. \(n=4p+1\).
When \(p=2\), \(K_9\) admits a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition whenever \(\alpha+\beta+\gamma=9\) by Lemmas 4.1, 4.7, and Theorem 4.2. For \(p\geq4\), we write \[K_{4p+1}=K_8\oplus K_{4(p-2)+1}\oplus K_{8,4(p-2)+1}.\] With an argument similar to that of Case 1, the proof follows. ◻
Theorem 4.9. Let \(n\ge8\). Then \(K_n\) admits a \(\{P_5^{\alpha},S_5^{\beta},Y_5^{\gamma}\}\)-decomposition if and only if \[\alpha+\beta+\gamma=\frac{n(n-1)}{8}\] and \[n\equiv0 \text{ or } 1 \pmod{8}.\]
Proof. Suppose that \(K_n\) admits a \(\{P_5^{\alpha},S_5^{\beta},Y_5^{\gamma}\}\)-decomposition. From the definition of admissible triplets, we have \[4(\alpha+\beta+\gamma)=\binom{n}{2}.\] Therefore, \[n(n-1)\equiv0\pmod{8},\] which implies that \[n\equiv0,1\pmod{8}.\] Conversely, suppose that \(n\ge8\) and \(n\equiv0\) or \(1\pmod{8}\). Then \(n=4p\) or \(4p+1\) with \(p\) even. By Lemma 4.8, \(K_n\) admits a \(\{P_5^{\alpha},S_5^{\beta},Y_5^{\gamma}\}\)-decomposition whenever \[\alpha+\beta+\gamma=\frac{n(n-1)}{8}.\] This completes the proof. ◻
This paper determines the necessary and sufficient conditions for the \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition of \(K_{m,n}\) and \(K_n\). The main result for \(K_{m,n}\) is stated in Theorem 3.21. For \(m\ge4\) and \(n\ge2\), a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition exists if and only if \[\alpha+\beta+\gamma=\frac{mn}{4} \quad\text{and}\quad mn\equiv0\pmod{4},\] subject to the additional parity condition in the case \(m=2p\), \(p\geq2\), \(n=2\), and to the excluded admissible triplets in the cases \(m=4p\), \(n=3\), and \(m=4\), \(n\geq4\). For complete graphs, Theorem 4.9 shows that \(K_n\) admits a \(\{P_5^\alpha,S_5^\beta,Y_5^\gamma\}\)-decomposition if and only if \[n\equiv0 \text{ or } 1 \pmod{8},\] with \(n\ge8\).
The admissible triplets \((\alpha, \beta, \gamma )\) are obtained by summing the contributions of the constituent subgraphs in each decomposition. The corresponding values are listed below.
| Decomposition | \((\alpha,\beta,\gamma)\) | Component-wise sum |
|---|---|---|
| \(K_{6,6}=K_{6,4}\oplus K_{6,2}\) | \((1 , 1, 7)\) | \(( 0, 1,5 ) + ( 1, 0, 2)\) |
| \((1, 2, 6)\) | \(( 0,2 , 4) + (1 ,0 ,2 )\) | |
| \((1,3 , 5)\) | \(( 0, 3, 3) + (1 , 0,2 )\) | |
| \((1 ,4 , 4)\) | \(( 0, 4,2 ) + ( 1, 0,2 )\) | |
| \((1 , 5, 3)\) | \(( 1, 4, 1) + (0 , 1, 2)\) | |
| \((1, 6, 2)\) | \((0 , 6, 0) + ( 1,0 , 2)\) | |
| \(( 2, 1, 6)\) | \((1 , 1, 4) + ( 1, 0,2 )\) | |
| \(( 2, 2,5 )\) | \((1 ,2 ,3 ) + (1 ,0 ,2 )\) | |
| \((2 ,3 ,4 )\) | \(( 1,3 ,2 ) + ( 1, 0,2 )\) | |
| \(( 2, 4, 3)\) | \((1 , 4, 1) + (1 ,0 ,2 )\) | |
| \((2, 5,2 )\) | \(( 1, 3, 2) + (1 ,2 ,0 )\) | |
| \((2 ,6 ,1 )\) | \((1 ,4 ,1 ) + ( 1, 2, 0)\) | |
| \(( 3, 1, 5)\) | \((2 , 1, 3) + (1 , 0, 2)\) | |
| \((3 , 2, 4)\) | \((2 , 2, 2) + ( 1,0 ,2 )\) | |
| \(( 3, 3,3 )\) | \((2 , 3,1 ) + (1 ,0 , 2)\) | |
| \((3 ,4 ,2 )\) | \((2 , 4,0 ) + (1 ,0 ,2 )\) | |
| \(( 3, 5,1 )\) | \(( 2, 3, 1) + (1 , 2, 0)\) | |
| \((4 , 1, 4)\) | \((1 , 1, 4) + (3 ,0 , 0)\) | |
| \((4 , 2, 3)\) | \(( 1, 2, 3) + ( 3,0 ,0 )\) | |
| \(( 4, 3,2 )\) | \(( 1, 3,2 ) + (3 ,0 , 0)\) | |
| \(( 4, 4, 1)\) | \(( 1, 4, 1) + ( 3, 0,0 )\) | |
| \(( 5, 1, 3)\) | \(( 2, 1, 3) + ( 3, 0, 0)\) | |
| \(( 5, 2, 2)\) | \((2 , 2,2 ) + (3 , 0, 0)\) | |
| \((5 , 3,1 )\) | \(( 2, 3,1 ) + ( 3,0 , 0)\) | |
| \((6 ,1 ,2 )\) | \(( 3, 1, 2) + (3 , 0,0 )\) | |
| \(( 6, 2,1)\) | \(( 3, 2,1 ) + ( 3, 0,0 )\) | |
| \((7 ,1 ,1 )\) | \(( 4, 1, 1) + ( 3, 0, 0)\) |
| Decomposition | \((\alpha,\beta,\gamma)\) | Component-wise sum |
|---|---|---|
| \(K_9 = 1G_1 \oplus 3G_2 \oplus 1S_5\) | \((0,1,6)\) | \((0,0,2)+(0,0,2)+(0,0,2)+(0,1,0)\) |
| \((0,2,5)\) | \((0,1,1)+(0,0,2)+(0,0,2)+(0,1,0)\) | |
| \((0,3,4)\) | \((0,2,0)+(0,0,2)+(0,0,2)+(0,1,0)\) | |
| \((0,4,3)\) | \((0,2,0)+(0,1,1)+(0,0,2)+(0,1,0)\) | |
| \((0,5,2)\) | \((0,2,0)+(0,2,0)+(0,0,2)+(0,1,0)\) | |
| \((0,6,1)\) | \((0,1,1)+(0,2,0)+(0,2,0)+(0,1,0)\) | |
| \((1,1,5)\) | \((0,0,2)+(0,0,2)+(1,0,1)+(0,1,0)\) | |
| \((1,2,4)\) | \((0,0,2)+(1,0,1)+(0,1,1)+(0,1,0)\) | |
| \((1,3,3)\) | \((1,0,1)+(0,2,0)+(0,0,2)+(0,1,0)\) | |
| \((1,4,2)\) | \((1,0,1)+(0,1,1)+(0,2,0)+(0,1,0)\) | |
| \((1,5,1)\) | \((1,0,1)+(0,2,0)+(0,2,0)+(0,1,0)\) | |
| \(K_{8}=1T_2 \oplus 2G_2 \oplus 1P_5\) | \((2,1,4)\) | \((1,1,0)+(0,0,2)+(0,0,2)+(1,0,0)\) |
| \((2,2,3)\) | \((1,1,0)+(0,1,1)+(0,0,2)+(1,0,0)\) | |
| \((2,3,2)\) | \((1,1,0)+(0,2,0)+(0,0,2)+(1,0,0)\) | |
| \((2,4,1)\) | \((1,1,0)+(0,1,1)+(0,2,0)+(1,0,0)\) | |
| \((3,1,3)\) | \((2,0,0)+(0,1,1)+(0,0,2)+(1,0,0)\) | |
| \((3,2,2)\) | \((2,0,0)+(0,2,0)+(0,0,2)+(1,0,0)\) | |
| \((3,3,1)\) | \((2,0,0)+(0,2,0)+(0,1,1)+(1,0,0)\) | |
| \((4,1,2)\) | \((2,0,0)+(1,0,1)+(0,1,1)+(1,0,0)\) | |
| \((4,2,1)\) | \((2,0,0)+(1,0,1)+(0,2,0)+(1,0,0)\) |
| Decomposition | \((\alpha,\beta,\gamma)\) | Component-wise sum |
|---|---|---|
| \(K_9 = 1G_1 \oplus 3G_2 \oplus 1S_5\) | \((0,1,6)\) | \((0,0,2)+(0,0,2)+(0,0,2)+(0,1,0)\) |
| \((0,2,5)\) | \((0,1,1)+(0,0,2)+(0,0,2)+(0,1,0)\) | |
| \((0,3,4)\) | \((0,2,0)+(0,0,2)+(0,0,2)+(0,1,0)\) | |
| \((0,4,3)\) | \((0,2,0)+(0,1,1)+(0,0,2)+(0,1,0)\) | |
| \((0,5,2)\) | \((0,2,0)+(0,2,0)+(0,0,2)+(0,1,0)\) | |
| \((0,6,1)\) | \((0,1,1)+(0,2,0)+(0,2,0)+(0,1,0)\) | |
| \((1,1,5)\) | \((0,0,2)+(0,0,2)+(1,0,1)+(0,1,0)\) | |
| \((1,2,4)\) | \((0,0,2)+(1,0,1)+(0,1,1)+(0,1,0)\) | |
| \((1,3,3)\) | \((1,0,1)+(0,2,0)+(0,0,2)+(0,1,0)\) | |
| \((1,4,2)\) | \((1,0,1)+(0,1,1)+(0,2,0)+(0,1,0)\) | |
| \((1,5,1)\) | \((1,0,1)+(0,2,0)+(0,2,0)+(0,1,0)\) | |
| \(K_{8}=1T_2 \oplus 2G_2 \oplus 1P_5\) | \((2,1,4)\) | \((1,1,0)+(0,0,2)+(0,0,2)+(1,0,0)\) |
| \((2,2,3)\) | \((1,1,0)+(0,1,1)+(0,0,2)+(1,0,0)\) | |
| \((2,3,2)\) | \((1,1,0)+(0,2,0)+(0,0,2)+(1,0,0)\) | |
| \((2,4,1)\) | \((1,1,0)+(0,1,1)+(0,2,0)+(1,0,0)\) | |
| \((3,1,3)\) | \((2,0,0)+(0,1,1)+(0,0,2)+(1,0,0)\) | |
| \((3,2,2)\) | \((2,0,0)+(0,2,0)+(0,0,2)+(1,0,0)\) | |
| \((3,3,1)\) | \((2,0,0)+(0,2,0)+(0,1,1)+(1,0,0)\) | |
| \((4,1,2)\) | \((2,0,0)+(1,0,1)+(0,1,1)+(1,0,0)\) | |
| \((4,2,1)\) | \((2,0,0)+(1,0,1)+(0,2,0)+(1,0,0)\) | |
| \(K_9 = 1G_1 \oplus 6P_5 \oplus 1S_5\) | \((6,1,2)\) | \((0,0,2)+6(1,0,0)+(0,1,0)\) |
| \((6,2,1)\) | \((0,1,1)+6(1,0,0)+(0,1,0)\) | |
| \((7,1,1)\) | \((1,0,1)+6(1,0,0)+(0,1,0)\) |