Let \(K_n\), \(P_n\), and \(Y_n\) respectively denote a complete graph, a path, and a \(Y\)-tree on \(n\) vertices, and let \(K_{m,n}\) denote a complete bipartite graph with \(m\) and \(n\) vertices in its parts. Graph decomposition is the process of breaking down a graph into a collection of edge-disjoint subgraphs. A graph \(G\) has a \((H_1, H_2)\)-multi-decomposition if it can be decomposed into \(\alpha \geq 0\) copies of \(H_1\) and \(\beta \geq 0\) copies of \(H_2\), where \(H_1\) and \(H_2\) are subgraphs of \(G\). In this paper, we derive the necessary and sufficient conditions for the \((P_5, Y_5)\)-multi-decomposition of \(K_n\) and \(K_{m,n}\).
All graphs considered in this paper are finite, simple, and undirected. Let \(K_n\) denote a complete graph on \(n\) vertices, \(K_{m,n}\) a complete bipartite graph with vertex partite sets of cardinality \(m\) and \(n\), and \(P_k\) a path on \(k\) vertices. A \(Y\)-tree on \(k\) vertices, denoted by \(Y_k\), is a tree in which one edge is attached to a vertex \(v\) of the path \(P_{k-1}\) such that at least one of the adjacent vertices of \(v\) has degree 1.
A decomposition of a graph \(G\) is a set of edge-disjoint subgraphs \(H_1, H_2, \dots, H_r\) of \(G\) such that every edge of \(G\) belongs to exactly one \(H_i\), \(1 \leq i \leq r\). If all the subgraphs in the decomposition of \(G\) are isomorphic to a graph \(H\), then \(G\) is said to be \(H\)-decomposable. If \(G\) can be decomposed into \(\alpha\) copies of \(H_1\) and \(\beta\) copies of \(H_2\), then \(G\) is said to have an \((H_1, H_2)\)-multi-decomposition or an \(\{H_1^\alpha, H_2^\beta\}\)-decomposition. The pair \((\alpha, \beta)\) is called admissible if it satisfies the necessary conditions for the existence of an \(\{H_1^\alpha, H_2^\beta\}\)-decomposition. If \(G\) has an \((H_1, H_2)\)-multi-decomposition for all admissible pairs \((\alpha, \beta)\), it is said to have an \((H_1, H_2)_{\{\alpha, \beta\}}\)-decomposition.
The necessary and sufficient condition for the existence of a \(P_5\)-decomposition of complete graphs was studied in [5], and for complete bipartite graphs in [1]. The path decomposition of various graphs was explored in [15,11]. The graph \(Y_5\) is one of the three non-isomorphic trees of order five, excluding paths and stars. Caterina and Antonio [3] named \(Y_5\) as the chair and studied the stability number of chair-free graphs.
The \(Y_5\)-decomposition of complete graphs was obtained by C. Huang and A. Rosa [5]. J. Paulraj Joseph and A. Samuel Issacraj [8] referred to \(Y_5\) as the fork and studied its decomposition in complete bipartite graphs. S. Gomathi and A. Tamil Elakkiya [4] defined this graph as a \(Y_5\)-tree and investigated its decomposition in the tensor product of complete graphs. The \(Y_5\)-decomposition of various graphs was further analyzed in [9,10]. The concept of multi-decomposition was introduced by A. Abueida and M. Daven [2]. In recent years, multi-decomposition of graphs has emerged as a prominent research area in graph theory. T.-W. Shyu studied the multi-decomposition of complete graphs into paths with cycles and stars [12,13]. S. Jeevadoss and A. Muthusamy established necessary and sufficient conditions for the multi-decomposition of complete bipartite graphs into paths and cycles [6]. Multi-decomposition of complete bipartite graphs into paths and stars was considered in [14].
In this paper, we establish the necessary and sufficient conditions for the existence of a \((P_5, Y_5)\)-multi-decomposition of \(K_n\) and \(K_{m,n}\). To prove our results, we recall the following theorems:
| Case | \(k\) | \(m\) | \(n\) | Characterization |
| 1. | even | even | even | \(k \leq 2m, k \leq 2n,\) not both equal |
| 2. | odd | even | even | Equalities hold when \(k\) is even |
| 3. | even | even | odd | \(k \leq 2m – 2, k \leq 2n\) |
| 4. | even | odd | even | \(k \leq 2m, k \leq 2n – 2\) |
| 5. | even | odd | odd | Decomposition impossible |
| 6. | odd | even | odd | \(k \leq 2m – 1, k \leq n\) |
| 7. | odd | odd | even | \(k \leq m, k \leq 2n – 1\) |
| 8. | odd | odd | odd | \(k \leq m, k \leq n\) |
Next, we introduce a new graph structure called Conjoined Twins in the following remark.
The subgraphs induced by \(A\) and \(B\) are isomorphic to \(P_5\) when \(A = \{v_1, v_2, v_6, v_7, v_8\}\) and \(B = \{v_2, v_3, v_4, v_5, v_6\}\). Similarly, if \(A = \{v_1, v_2, v_3, v_4, v_8\}\) and \(B = \{v_4, v_5, v_6, v_7, v_8\}\), the corresponding induced subgraphs are isomorphic to \(Y_5\). We call these subsets of vertices Conjoined Twins \((T)\) because the subsets \(A\) and \(B\) are not disjoint (there are two common vertices), but the induced subgraphs are isomorphic.
It is interesting to note that the subgraph induced by \(A\) is isomorphic to \(P_5\) when \(A = \{v_1, v_2, v_3, v_8, v_6\}\), and if \(B = \{v_3, v_4, v_5, v_6, v_7\}\), the corresponding induced subgraph is isomorphic to \(Y_5\).
Thus, decomposing the graph \(G\) into a structure whose vertices are Conjoined Twins as in Figure 1 can be viewed as consisting of \(2\) copies of \(P_5\), \(2\) copies of \(Y_5\), or \(1\) copy each of \(P_5\) and \(Y_5\), which significantly simplifies the \((P_5, Y_5)\)-multi-decomposition.
For a subgraph \(H\) of \(G\), \(G \backslash H\) denotes a graph where \(V(G \backslash H) = V(G)\) and \(E(G \backslash H) = E(G) – E(H)\).
\(rG\) denotes \(r\) disjoint copies of the graph \(G\).
\(G = H_1 \oplus H_2\) means \(G\) can be decomposed into \(H_1\) and \(H_2\).
Let \(v_i\), \(1 \leq i \leq n\), be the vertices of the complete graph \(K_n\).
In the complete bipartite graph \(K_{m,n}\), the vertices of the first partite set with \(m\) vertices are denoted by \(v_{1i}\), \(1 \leq i \leq m\), and the second partite set with \(n\) vertices by \(v_{2j}\), \(1 \leq j \leq n\).
A path \(P_5\) with \(5\) vertices \(v_i\), \(1 \leq i \leq 5\), having \(v_1\) and \(v_5\) as pendant vertices is denoted by \(P_5(v_1, v_2, v_3, v_4, v_5)\).
The \(Y_5\) graph with \(5\) vertices \(v_i\), \(1 \leq i \leq 5\), is denoted by \(Y_5(v_1, v_2, \underline{v_3}, v_4; \underline{v_5})\), where \(v_i\), \(1 \leq i \leq 4\), form a path of length three, and the underlined vertices denote an edge \(v_3v_5\).
Suppose we have a graph whose vertices are Conjoined Twins \((T)\) as in Figure 1. We denote it by \(T(v_1, \underline{v_2}, v_3, v_4, v_5, \underline{v_6}, v_7; \underline{v_8})\), where \(v_i\), \(1 \leq i \leq 7\), form a path of length six, and the underlined vertices denote edges \(v_2v_8\) and \(v_6v_8\).
The following theorem gives the necessary condition for the existence of a multi-decomposition of the complete graph \(K_n\) into paths and \(Y\)-trees with 5 vertices.
Proof. Proof follows from the edge divisibility condition. ◻
In this section, we show that the necessary condition obtained in Theorem 2.4 is also sufficient for the existence of a multi-decomposition of \(K_n\), (\(n \geq 8\)) into \(P_5\) and \(Y_5\).
Proof. \(K_8 = 3 T \oplus 1 P_5\), where the \(3T\)’s and \(1P_5\) are given by, \[\begin{aligned} &T(v_6,\underline{v_7},v_5,v_1,v_4,\underline{v_8},v_2;\underline{v_3}), T(v_3,\underline{v_6},v_4,v_2,v_5,\underline{v_8},v_7;\underline{v_1}),\\ &T(v_8,\underline{v_6},v_5,v_3,v_1,\underline{v_7},v_4;\underline{v_2}), P_5(v_1,v_2,v_3,v_4,v_5). \end{aligned}\]
Similarly, \(K_9\) can be written as \(K_9 =4 T \oplus 1 P_5\), where the \(4T\)’s and \(1P_5\) are as follows: \[\begin{aligned} &T(v_3,\underline{v_6},v_4,v_1,v_8,\underline{v_7},v_5;\underline{v_2}), T(v_3,\underline{v_9},v_4,v_2,v_5,\underline{v_6},v_1;\underline{v_7}),\\ &T(v_4,\underline{v_8},v_5,v_3,v_1,\underline{v_9},v_2;\underline{v_6}), T(v_4,\underline{v_7},v_1,v_5,v_9,\underline{v_8},v_2;\underline{v_3}), P_5(v_1,v_2,v_3,v_4,v_5). \end{aligned}\] ◻
Proof. It is clear that \(K_{7,8} = 7 T\), where \(7T\)’s are given by, \[\begin{aligned} &T(v_{21},\underline{v_{11}},v_{23},v_{12},v_{24},\underline{v_{13}},v_{22};\underline{v_{25}}), T(v_{25},\underline{v_{12}},v_{22},v_{11},v_{{26}},\underline{v_{13}},v_{23};\underline{v_{21}}),\\ & T(v_{24},\underline{v_{11}},v_{28},v_{15},v_{26},\underline{v_{14}},v_{25};\underline{v_{27}}), T(v_{24},\underline{v_{14}},v_{28},v_{13},v_{27},\underline{v_{15}},v_{25};\underline{v_{23}}), \\ & T(v_{27},\underline{v_{12}},v_{28},v_{17},v_{24},\underline{v_{16}},v_{25};\underline{v_{26}}), T(v_{28},\underline{v_{16}},v_{21},v_{14},v_{22},\underline{v_{17}},v_{26};\underline{v_{27}}), \\ & T(v_{24},\underline{v_{15}},v_{22},v_{16},v_{23},\underline{v_{17}},v_{25};\underline{v_{21}}). \end{aligned}\]
Similarly \(K_{8,8} = 8 T\), where \(8T\)’s are identified as, \[\begin{aligned} &T(v_{22},\underline{v_{13}},v_{24},v_{12},v_{23},\underline{v_{18}},v_{21};\underline{v_{25}}), T(v_{28},\underline{v_{12}},v_{25},v_{11},v_{26},\underline{v_{13}},v_{23};\underline{v_{27}}), \\ & T(v_{26},\underline{v_{12}},v_{21},v_{13},v_{28},\underline{v_{14}},v_{25};\underline{v_{22}}), T(v_{28},\underline{v_{11}},v_{27},v_{14},v_{26},\underline{v_{15}},v_{25};\underline{v_{24}}), \\ & T(v_{24},\underline{v_{14}},v_{21},v_{16},v_{27},\underline{v_{15}},v_{22};\underline{v_{23}}), T(v_{24},\underline{v_{16}},v_{28},v_{15},v_{21},\underline{v_{17}},v_{26};\underline{v_{22}}),\\ & T(v_{21},\underline{v_{11}},v_{23},v_{17},v_{24},\underline{v_{18}},v_{27};\underline{v_{22}}), T(v_{23},\underline{v_{16}},v_{26},v_{18},v_{28},\underline{v_{17}},v_{27};\underline{v_{25}}). \end{aligned}\]
Further \(K_{9,8} = 9 T\), the following are the required \(9T\)’s \[\begin{aligned} &T(v_{26},\underline{v_{11}},v_{23},v_{12},v_{24},\underline{v_{13}},v_{25};\underline{v_{22}}), T(v_{25},\underline{v_{12}},v_{26},v_{19},v_{27},\underline{v_{13}},v_{23};\underline{v_{28}}), \\ & T(v_{22},\underline{v_{12}},v_{21},v_{13},v_{26},\underline{v_{14}},v_{23};v_{27}), T(v_{28},\underline{v_{11}},v_{24},v_{14},v_{22},\underline{v_{15}},v_{25};v_{27}), \\ & T(v_{21},\underline{v_{14}},v_{25},v_{16},v_{23},\underline{v_{15}},v_{24};\underline{v_{28}}), T(v_{27},\underline{v_{16}},v_{21},v_{15},v_{26},\underline{v_{17}},v_{22};\underline{v_{24}}),\\ & T(v_{21},\underline{v_{18}},v_{27},v_{17},v_{25},\underline{v_{19}},v_{22};\underline{v_{24}}), T(v_{22},\underline{v_{16}},v_{26},v_{18},v_{23},\underline{v_{17}},v_{21};\underline{v_{28}}),\\ & T(v_{22},\underline{v_{18}},v_{25},v_{11},v_{21},\underline{v_{19}},v_{23};\underline{v_{28}}). \end{aligned}\] ◻
Proof. The admissible pairs satisfying \(\alpha + \beta = 7\) are
{(0,7),(1,6),(2,5),(3,4),(4,3),(5,2),
(6,1),(7,0)}.
Case 1. \(\alpha \neq 0\).
From Lemma 2.5, \(K_8=3 T \oplus 1 P_5\), which can be taken into any of the forms: \(6Y_5 \oplus 1 P_5, 5Y_5 \oplus 2 P_5, 4Y_5 \oplus 3 P_5, 3Y_5 \oplus 4 P_5, 2Y_5 \oplus 5 P_5, 1Y_5 \oplus 6 P_5, \,\,\, \text{and} \,\,\, 7 P_5\) using Remark 2.2.
Thus we have \((P_5, Y_5)\) – multi-decomposition for the admissible pairs \((\alpha, \beta)\) \(\in \{(1,6),(2,5),(3,4),\\(4,3),(5,2),(6,1),(7,0)\}.\)
Case 2. \(\alpha = 0\).
Theorem 1.1 gives the required decomposition for the admissible pair \((0,7)\).
Hence the proof follows from Cases 1 & 2 for all admissible pairs \((\alpha, \beta)\). ◻
Proof. The admissible pairs satisfying \(\alpha + \beta = 9\) are
{(0,9),(1,8),(2,7),(3,6),(4,5),(5,4),
(6,3),(7,2),(8,1),(9,0)}.
Case 1. \(\alpha \neq 0\).
From Lemma 2.6, \(K_9=4 T \oplus 1 P_5\), which can be taken into any of the forms: \(8Y_5 \oplus 1 P_5,\\ 7Y_5 \oplus 2 P_5, 6Y_5 \oplus 3 P_5, 5Y_5 \oplus 4 P_5, 4Y_5 \oplus 5 P_5, 3Y_5 \oplus 6 P_5, 2Y_5 \oplus 7 P_5, 1Y_5 \oplus 8 P_5 \,\,\, \text{and} \,\,\, 9 P_5\) using Remark 2.2.
Thus we have \((P_5, Y_5)\) – multi-decomposition for the admissible pairs \((\alpha, \beta)\) \(\in \{(1,8),(2,7),(3,6),\\(4,5),(5,4),(6,3),(7,2),(8,1),(9,0)\}.\)
Case 2. \(\alpha = 0\).
Theorem 1.1 gives the required decomposition for the admissible pair \((0,9)\).
Thus, \(K_9\) admits \((P_5, Y_5)_{\{\alpha, \beta\}}\) – decomposition. ◻
Proof. The admissible pairs satisfying \(\alpha + \beta = 14\) are
{(0,14),(1,13),(2,12),(3,11),(4,10),(5,9),(6,8),
(7,7),(8,6),(9,5),(10,4),(11,3),(12,2),(13,1),(14,0)}.
From Lemma 2.6, \(K_{7,8}=7 T\), which can be taken into any of the forms: \(14 Y_5, 13 Y_5 \oplus 1 P_5, 12 Y_5 \oplus 2 P_5, 11 Y_5 \oplus 3 P_5, 10 Y_5 \oplus 4 P_5, 9 Y_5 \oplus 5 P_5, 8 Y_5 \oplus 6 P_5, 7 Y_5 \oplus 7 P_5, 6 Y_5 \oplus 8 P_5, 5 Y_5 \oplus 9 P_5, 4 Y_5 \oplus 10 P_5, 3 Y_5 \oplus 11 P_5, 2 Y_5 \oplus 12 P_5, 1 Y_5 \oplus 13 P_5 \,\,\, \text{and} \,\,\, 14 P_5\) using Remark 2.2.
Thus we have \((P_5, Y_5)\) – multi-decomposition for all the admissible pairs \((\alpha, \beta)\). ◻
Proof. The admissible pairs satisfying \(\alpha + \beta = 16\) are
{(0,16),(1,15),(2,14),(3,13),(4,12),(5,11),(6,10),
(7,9),(8,8),(9,7),(10,6),(11,5),(12,4),(13,3),(14,2),(15,1),(16,0)}.
From Lemma 2.6 , \(K_{8,8}=8 T\). Then we have \((P_5, Y_5)\) – multi-decomposition for all the admissible pairs \((\alpha, \beta)\) using Remark 2.2. ◻
Proof. The admissible pairs satisfying \(\alpha + \beta = 18\) are {\((0,18),(1,17),(2,16),(3,15),(4,14),(5,13),(6,12),(7,11),(8,10),(9,9),(10,8),(11,7),(12,6),(13,5),(14,4),\)\((15,3),(16,2),(17,1),(18,0)\)}.
From Lemma 2.6 , \(K_{9,8}=9 T\). Then we have \((P_5, Y_5)\) – multi-decomposition for all the admissible pairs \((\alpha, \beta)\) using Remark 2.2. ◻
Proof. From the given (Necessary conditions) edge
divisibility condition,
we have \(n\equiv 0\,\,\, \text{or}\,\,\,1
\,\,\,(mod \,\,\, 8)\).
Case 1: \(n\equiv 0\hspace{.06cm} \hspace{.01cm}(mod \,\,\, 8)\).
Let \(n=4t\), \(t\) is even. We prove this theorem using induction on \(t\). When \(t=2\), the proof follows from Lemma 2.7. We observe that for \(t\geq 4\), \[\label{1} K_{4t}=K_{4(t-2)} \oplus K_9 \oplus K_{4(t-2)-1,8} . \tag{1}\]
Also for \(t\geq 6\), \[\label{2} K_{4(t-2)-1,8}=K_{4(t-4)-1,8} \oplus K_{8,8} . \tag{2}\]
From (1) and (2), \[\label{3rr} K_{4t}=K_{4(t-2)} \oplus K_9 \oplus K_{4(t-4)-1,8} \oplus K_{8,8}, \hspace{.3cm} t \geq 6 . \tag{3}\]
Assume that the theorem is true for all even \(k\) \(<\) \(t\). We have to prove for \(t=k+2\). From (3), we can write, \[K_{4(k+2)}=K_{4k} \oplus K_9 \oplus K_{4(k-2)-1,8} \oplus K_{8,8} .\]
By induction hypothesis and from Lemmas 2.7, 2.8, 2.9 and 2.10 the proof follows.
Case 2: \(n\equiv 1\hspace{.06cm} \hspace{.01cm}(mod \,\,\, 8)\).
Let \(n=4t+1\), \(t\) is even. When \(t=2\), the proof follows from Lemma 2.8. We observe that for \(t\geq 4\), \[\label{3} K_{4t+1}=K_{4(t-2)} \oplus K_9 \oplus K_{4(t-2)+\frac{1}{2}(t-2),8} \tag{4}\] Also for \(t\geq 6\), \[\label{4} K_{4(t-2)+\frac{1}{2}(t-2),8}=K_{4(t-4)+\frac{1}{2}(t-2),8} \oplus K_{9,8} . \tag{5}\]
From (4) and (5), \[\label{5} K_{4t+1}=K_{4(t-2)} \oplus K_9 \oplus K_{4(t-4)+\frac{1}{2}(t-2),8} \oplus K_{9,8}, \hspace{.3cm} t \geq 6 . \tag{6}\]
Assume that the theorem is true for all even \(k\) \(<\) \(t\). We have to prove for \(t=k+2\). From (6), we can write, \[K_{4(k+2)+1}=K_{4k} \oplus K_9 \oplus K_{4(k-2)+\frac{1}{2}k,8} \oplus K_{9,8} .\]
By induction hypothesis and from Lemmas 2.7, 2.8 and 2.11 the proof follows. ◻
Proof. The proof follows from Theorems 2.4 and 2.12. ◻
In this section, we derive the necessary conditions for the existence of multi-decomposition of \(K_{m,n}\), (\(m>2, n\geq 2\)) into paths and \(Y\)-trees with 5 vertices.
Proof. Let \(V(K_{2k,2})=V_1 \cup V_2\), where \(|V_1|=2k\), \(|V_2|=2\) and \(|E(K_{2k,2})|=4k\). \(P_5\) has a degree sequence \((2,2,2,1,1)\). While decomposing \(K_{2k,2}\) into \(P_5\)’s and \(Y_5\)’s, the two vertices of \(P_5\) with degree 2 which are incident with a vertex of degree 1, should be formed using the vertex set \(V_2=\) {\(v_{21},v_{22}\)}. \(Y_5\) has a degree sequence \((3,2,1,1,1)\). Here, the vertex with degree 3 and the vertex with degree 1 which is incident with a vertex of degree 2, should be formed using the vertex set \(V_2\). Since each vertex in \(V_2\) has degree \(2k\), after decomposing \(K_{2k,2}\) into \(\alpha\) number of \(P_5\), each vertex \(v_{2i}\), \(i=1,2\) has degree \(2k-2\alpha\) and \(|E(K_{2k,2}\backslash \alpha P_5)|=4k-4\alpha\). Since \(k\) is even, it is clear that \[\begin{aligned} 2(k-\alpha) \equiv \left\{ \begin {aligned} & 0 (mod \,\, 4),\,\,\, if\,\,\,\,\alpha \,\,\, is\,\,\,even,\\ & 2 (mod \,\, 4),\,\,\, if\,\,\,\alpha\,\,\,is\,\,\,odd. \end{aligned} \right. \end{aligned}\] Therefore, partitioning the remaining \(4(k-\alpha)\) edges into \(k-\alpha\) number of \(Y_5\) is possible only when \(\alpha\) is even. ◻
Proof. The proof is same as Lemma 3.1 with the same argument. Since \(k \geq 3\) is odd, \[\begin{aligned} 2(k-\alpha) \equiv \left\{ \begin {aligned} & 2 (mod \,\, 4),\,\,\, if\,\,\,\,\alpha \,\,\, is\,\,\,even,\\ & 0 (mod \,\, 4),\,\,\, if\,\,\,\alpha\,\,\,is\,\,\,odd. \end{aligned} \right. \end{aligned}\] Hence the proof follows. ◻
\(m=2k\), \(k\) even; \(n=2\) and \(\alpha\) is odd
\(m=2k\), \(k \geq 3\) odd; \(n=2\) and \(\alpha\) is even
Proof. The proof follows from edge divisibility condition and by Lemmas 3.1 and 3.2. ◻
In the following lemmas we prove that the above necessary conditions are also sufficient.
Proof. By Theorem 3.3, \(\alpha + \beta = 2\). Hence the admissible pairs \((\alpha, \beta)\) are \((0,2)\), \((1,1)\) and \((2,0)\). By Theorem 1.2, \(K_{4,2}\) can be decomposed into \(2P_5\) and by Theorem 1.3, \(K_{4,2}\) can be decomposed into \(2Y_5\). Hence there exists a \((P_5,Y_5)\) – multi-decomposition for the admissible pairs \((0,2)\) and \((2,0)\). By Lemma 3.1, it is clear that there does not exist a \((P_5,Y_5)\) – multi-decomposition for the admissible pair \((1,1)\). Hence the proof. ◻
Proof. The admissible pairs for which the decomposition exists are (\(\alpha, \beta\)) \(\in\) {(3,0), (1,2)}. For \((3,0)\), Theorem 1.2 gives the required decomposition. For \((1,2)\), we have the necessary breakdown is as follows:
\[P_5(v_{11},v_{21},v_{12},v_{22},v_{13}),Y_5(v_{21},v_{15},\underline{v_{22}},v_{14};\underline{v_{11}}),Y_5(v_{22},v_{16},\underline{v_{21}},v_{14};\underline{v_{13}}).\]
The desired decomposition does not exist for the admissible pairs \((2,1)\) and \((0,3)\) by Lemma 3.2. ◻
Proof. Since \(k\) is even, \(k=2k_1\) for \(k_1\) \(\in\) \(\mathbb{N}\). we write, \(K_{2k,2} = k_1 K_{4,2}\).
Therefore, by Lemma 3.4, for any even \(\alpha\) such that \(\alpha + \beta = k\), there exists a \((P_5, Y_5)\) – multi-decomposition for the admissible pairs \((\alpha, \beta)\) with \(\alpha\), \(\beta\) are even. This completes the proof. ◻
Proof. Since \(k \neq 1\) is odd, \(k=2q+1\) for \(q\) \(\in\) \(\mathbb{N}\). we write, \(K_{2k,2}= (q-1)K_{4,2} \oplus K_{6,2}\).
Therefore, by Lemmas 3.4 and 3.5, for any odd \(\alpha\) such that \(\alpha + \beta = k\), there exists a \((P_5, Y_5)\) – multi-decomposition for the admissible pairs \((\alpha, \beta)\) with \(\alpha\) is odd and \(\beta\) is even. This completes the proof. ◻
Proof. Case 1: (3,0).
Theorem 1.2 gives required 3\(P_5\)’s.
Case 2: (2,1).
\[P_5(v_{21},v_{12},v_{22},v_{11},v_{23}), P_5(v_{11},v_{21},v_{13},v_{22},v_{14}), Y_5(v_{21},v_{14},\underline{v_{23}},v_{13};\underline{v_{12}}).\]
Case 3: (1,2).
\[P_5(v_{21},v_{14},v_{22},v_{11},v_{23}), Y_5(v_{22},v_{12},\underline{v_{23}},v_{13};\underline{v_{14}}), Y_5(v_{22},v_{13},\underline{v_{21}},v_{12};\underline{v_{11})}.\]
Case 4: (0,3).
Theorem 1.3 gives the required decomposition. ◻
Proof. Case 1: \(\alpha\) is even i.e.,\((\alpha, \beta)\) \(\in\) {(4,0), (2,2), (0,4)}.
Since \(K_{4,4}=2K_{4,2}\), Theorems 1.2 and 1.3 give the required decomposition.
Case 2: \(\alpha\) is odd.
Subcase 1: (3,1). \[P_5(v_{11},v_{22},v_{14},v_{23},v_{13}), P_5(v_{21},v_{14},v_{24},v_{12},v_{22}), P_5(v_{12},v_{23},v_{11},v_{24},v_{13}), Y_5(v_{22},v_{13},\underline{v_{21}},v_{12};\underline{v_{11}})\]
Subcase 2: (1,3). \[P_5(v_{12},v_{22},v_{13},v_{21},v_{14}), Y_5(v_{13},v_{23},\underline{v_{14}},v_{24};\underline{v_{22}}), Y_5(v_{13},v_{24},\underline{v_{11}},v_{23};\underline{v_{22}}), Y_5(v_{11},v_{21},\underline{v_{12}},v_{24};\underline{v_{23}})\] ◻
Proof. We can write \(K_{4,5}= K_{4,2} \oplus K_{4,3}\), \(K_{4,6}=2 K_{4,3}\). Then the proof follows from Lemmas 3.4 and 3.8. ◻
Proof. We can write \(K_{6,6}= K_{4,6} \oplus K_{2,6}\). Since \(K_{m,n}\cong K_{n,m}\), the proof follows from Lemmas 3.5 and 3.10. ◻
Proof. Let \(n= 4q + r\) for \(q>0\) and \(r \in \{0,1,2,3\}\).
If \(r=0\), \(K_{4k,n} = K_{4k,4q} = kq K_{4,4}\).
For \(r=1\), \(K_{4k,n} = K_{4k,4q+1} = K_{4k,4(q-1)+5}= k(q-1) K_{4,4} \oplus K_{4,5}\).
When \(r=2\), \(K_{4k,n} = K_{4k,4q+2} = K_{4k,4(q-1)+6}= k(q-1) K_{4,4} \oplus K_{4,6}\).
When \(r=3\), \(K_{4k,n} = K_{4k,4q+3} = kqK_{4,4} \oplus K_{4,3}\).
Then the proof follows from Lemmas 3.8, 3.9, 3.10 and by mathematical induction on \(k\), \(n\). ◻
Proof. Since \(k_1 \neq 1\), \(k_2 \neq 1\) are odd, \(k_1=2q_1 + 1\) and \(k_2=2q_2 + 1\) for \(q_1, q_2 \in \mathbb{N}\) and we write, \(K_{2{k_1}, 2{k_2}}= (q_1-1)(q_2-1)K_{4,4} \oplus (q_1-1) K_{4,6} \oplus (q_2-1) K_{6,4} \oplus K_{6,6}\).
Then the proof follows from Lemmas 3.9, 3.10, 3.11 and by mathematical induction on \(k_1\), \(k_2\). ◻
Proof. Case 1: \(m \equiv 0 \,\,\,(mod\,\,\, 4)\) or \(n \equiv 0 \,\,\,(mod\,\,\, 4)\), w.l.o.g, let \(m=4k\) for \(k \in \mathbb{N}\).
Subcase 1.1. \(n=2\).
Lemma 3.6 gives the required decomposition.
Subcase 1.2. \(n\geq 3\).
Lemma 3.12 gives the required decomposition.
Case 2: \(m \equiv 0 \,\,\,(mod\,\,\, 2)\) and \(n \equiv 0 \,\,\,(mod\,\,\, 2)\), i.e., \(m=2k_1\), \(n=2k_2\) for \(k_1\), \(k_2\) \(\in \mathbb{N}\).
Subcase 2.1. When one of them is \(2\), w.l.o.g, let \(n=2\).
When \(k_1\) is even, this falls in Subcase 1.1. If \(k_1 \neq 1\) is odd, Lemma 3.7 gives the required decomposition.
Subcase 2.2. \(m,n > 2\).
When one of \(k_1\) and \(k_2\) or both of them are even, then the proof follows from Subcase 1.2. If both of them are odd, Lemma 3.13 gives the required decomposition. ◻
\(m=2k, k\) is even, \(n=2\) and \(\alpha\) is even.
\(m=2k,k \geq 3\) is odd, \(n=2\) and \(\alpha\) is odd.
\(m=4k\) and \(n \geq 3\).
\(m=2k_{1}\) and \(n=2k_{2}\); where \(k_{1},k_{2} \geq 3\) are odd.
Proof. Proof follows from Theorems 3.3 and 3.14. ◻
In this paper, it is proved that the necessary and sufficient condition for the existence of the \((P_5, Y_5)_{\{\alpha, \beta\}}\) – decomposition of the complete graph \(K_n\) (\(n\geq 8\)) is \(n\equiv 0\,\,\, or \,\,\,1 \,\,\,(mod \,\,\, 8)\). Also we have obtained the necessary and sufficient conditions for the \((P_5, Y_5)_{\{\alpha, \beta\}}\) – decomposition of the complete bipartite graph \(K_{m,n}\) (\(m > 2\), \(n \geq 2\)) as \(mn = 4(\alpha + \beta)\) whenever
\(m=2k\), \(k\) even; \(n=2\) then \(\alpha\) is even.
\(m=2k\), \(k \geq 3\) odd; \(n=2\) then \(\alpha\) is odd.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.