Menu
\(Y_k\)-tree is defined as \((v_1, v_2,\ldots, v_{k-1};\, v_{k-2} v_k)\) by taking their vertices as \((v_1,\,v_2,\ldots,\,v_k)\) and edges as \(\{(v_1v_2, v_2v_3,\ldots, v_{k-2}v_{k-1})\cup (v_{k-2}v_k)\}\). It is also represented as \((P_ {k-1} +e)\). One can obtain the necessary condition as \(mn(m-1)(n-1)\equiv 0 \pmod {2(k-1)}\), for \(k \geq 5\) to establish a \(Y_k\)-tree decomposition in \(K_m \times K_n\). Here the tensor product is denoted by \(\times\). In this manuscript, it is shown that a \(Y_5\)-tree (gregarious \(Y_5\)-tree) decomposition exists in \(K_m \times K_n\), if and only if, \(mn(m-1)(n-1)\equiv 0 \pmod8\).
A decomposition of graph \(G\) is a collection of subgraphs \(\{G_ i,\, 1\leq i \leq n\}\), in which each subgraph, is mutually – distinct by their edges along with \(E(G) = \cup_{i=1}^{n} E(G_i)\). Let \(K_n\) and \(P_n\) respectively denotes complete graph and path, on \(n\) vertices. \(Y_k\)-tree is defined as \((v_1, v_2,\ldots, v_{k-1};\, v_{k-2} v_k)\) by taking their vertices as \((v_1,\,v_2,\ldots,\,v_k)\) and edges as \(\{(v_1v_2, v_2v_3,\ldots, v_{k-2}v_{k-1})\cup (v_{k-2}v_k)\}\). It is also represented as \((P_ {k-1} +e)\). \(Y_5\)-tree or \((P_4 +e)\) graph, defined as \(\{v_1, v_2, v_3, v_4; v_3 v_5\}\), which is depicted in Figure 1.
The tensor product\((\times)\) of \(K_m\) and \(K_n\) be defined in this way: \(V(K_m \times K_n) = \{(p,q) \mid p \in V(K_m), q \in V(K_n)\}\) and \(E(K_m \times K_n) = \{(p,q)(r,s) \mid pr \in E(K_m)\) and \(qs \in E(K_n) \}\). Let it be taken as \(V (K_m \times K_n) = \{\bigcup \limits_{i=1}^m i_j,\, 1\leq j \leq n \}\), by considering \(V (K_m) = \{1, 2, \ldots, m\}\) and \(V (K_n) = \{1, 2, \ldots, n\}\). For instance, see Figure 2.
As all are aware of that tensor product has commutative and distributive properties. So we write as \(K_m \times K_n \simeq K_n \times K_m\) (commutative). If we have a \(Y_5\)-tree decomposition for \(K_m\), we then write \(K_m = Y_5 \oplus Y_5 \oplus \ldots \oplus Y_5\). By applying the distributive properties, we can write as \(K_m \times K_n = [(Y_5 \oplus Y_5 \oplus \ldots \oplus Y_5) \times K_n] \simeq [(Y_5 \times K_n) \oplus (Y_5 \times K_n) \oplus \ldots \oplus (Y_5 \times K_n)]\). If \(Y_5\)-tree decomposition arises in \(K_m \times K_n\), in addition to, if every vertex of each \(Y_5\)-tree’s is placed in different partite sets, then it called as gregarious \(Y_5\)-tree decomposition.
Tree decomposition and its special properties such as resolvable tree
decompositions are considered by many authors. Ringel [1] has conjectured that \(K_ {2m+1}\) can be decomposed as tree
having \(m\) edges. C. Huang and A.
Rosa [2] has proved that
\(Y_5\)-tree decomposition for \(K_m\) holds if and only if \(m\equiv 0,1 \pmod 8\). A \(G\)-decomposition of \(K_m\) have been investigated in [3], where \(|V(G)| = 5\). Inspired from Ringel
conjecture, G. Sethuraman and V. Murugan [4] has conjectured that, for \(m \geq 1\), \((G,
H)\)-decomposition exists in \(K_{4m+1}\), when the size of tree \(G\) and \(H\) is \(m\). Followed by these results, many
authors have begun to look into, tree decomposition in various graphs.
To know more about it, refer [5,6,7,8,9,10,11]. As a development of it,
gregarious tree decomposition in the tensor product of complete graph
has been started to investigate followed by the given results. A. Tamil
Elakkiya and A. Muthusamy [12] have been proved a gregarious kite
decomposition of \(K_m \times K_n\), if
and only if, \(mn(m-1)(n-1)\equiv 0 \pmod
8\). A. Tamil Elakkiya and A. Muthusamy [13] have been proved a gregarious kite
factorization of \(K_m \times K_n\), if
and only if, \(mn \equiv 0 \pmod 4\)
and \((m-1)(n-1)\equiv 0 \pmod 2\). In
this way, we focus on the \(Y_5\)-tree
(gregarious \(Y_5\)-tree) decomposition
of tensor product of complete graphs. In this manuscript, we establish a
\(Y_5\)-tree decomposition (gregarious
\(Y_5\)-tree) of \(K_m \times K_n\), if and only if, \(mn(m-1)(n-1)\equiv 0\pmod 8\).
\(Y_5\)-tree decomposition falls on the
cases given below:
(i) \(m \equiv 0 \pmod 4\) and for all
\(n\), \(n
\geq 2\).
(ii) \(m \equiv 1 \pmod 4\) and for all
\(n\), \(n
\geq 2\).
(iii) \(m \equiv 3 \pmod 4\) and \(n \equiv 0 \pmod 4\).
(iv) \(m \equiv 3 \pmod 4\) and \(n \equiv 1 \pmod 4\).
(v) \(m \equiv 2 \pmod 4\) and \(n \equiv 0 \pmod 4\).
(vi) \(m \equiv 2 \pmod 4\) and \(n \equiv 1 \pmod 4\).
Also we prove a gregarious \(Y_5\)-tree
decomposition in \(K_m \times K_n\) for
the following cases:
(i) \(m \equiv 0, 1 \pmod 8\) and for
all \(n\), \(n \geq 2\).
(ii) \(m \equiv 5 \pmod 8\) and for all
\(n\), \(n
\geq 2\).
(iii) \(m \equiv 4 \pmod 8\) and for
all \(n\), \(n \geq 2\).
(iv) \(m \equiv 6 \pmod 8\) and \(n = 4\).
(v) \(m \equiv 7 \pmod 8\) and \(n = 4\).
(vi) \(m \equiv 10 \pmod 8\) and \(n = 4\).
(vii) \(m \equiv 11 \pmod 8\) and \(n = 4\).
In order to prove our main result, we require the following:
Theorem 1. [2] \(Y_5\)-tree decompositions holds in \(K_m\) if and only if \(m\equiv 0, 1 \pmod 8\).
Lemma 1. \(K_4 \times K_n\) admits a \(Y_5\)-tree decomposition for all \(n, n\geq2\).
Proof. Since for every \(K_n\) has a \(K_2\) decomposition, we then write as
\(K_4 \times K_n = K_4 \times [K_2\oplus K_2
\oplus \ldots \oplus K_2] = (K_4 \times K_2 ) \oplus (K_4 \times K_2 )
\oplus \ldots \oplus (K_4 \times K_2 )\). By taking as \(V(K_4 \times K_2)= \{\bigcup \limits_{i=1}^4
i_j,\, 1\leq j \leq 2\}\), the following set \(\{(1_1, 2_2, 4_1, 3_2; 4_1 1_2), (1_1, 4_2, 3_1,
1_2; 3_1 2_2), (1_1, 3_2, 2_1, 4_2; 2_1 1_2)\}\), proves a \(Y_5\)-tree decomposition exists in \(K_4 \times K_2\). Thus, we obtain a \(Y_5\)-tree decomposition for \(K_4 \times K_n\).
Lemma 2. \(Y_5\times K_n\) admits a \(Y_5\)-tree decomposition for all \(n, n\geq2\).
Proof. As discussed in Lemma 1, we can take \(Y_5 \times K_n = Y_5 \times [K_2 \oplus K_2 \oplus \ldots \oplus K_2] = (Y_5 \times K_2) \oplus (Y_5 \times K_2) \oplus \ldots \oplus (Y_5 \times K_2)\). By taking as \(V(Y_5 \times K_2)= \{\bigcup\limits_{i=1}^5 i_j,\,1\leq j \leq2\}\), the following set \(\{(1_1, 2_2, 3_1, 4_2; 3_1 5_2), (1_2, 2_1, 3_2, 4_1; 3_2 5_1)\}\), proves a \(Y_5\)-tree decomposition exists in \(Y_5 \times K_2\). Thus, we obtain a \(Y_5\)-tree decomposition for \(Y_5 \times K_n\).
Lemma 3. \(K_{4,\,4} \times K_n\) admits a \(Y_5\)-tree decomposition for all \(n, n\geq2\).
Proof. Let us write as \(K_{4,\,4}
\times K_n = K_{4,\,4} \times [K_2\oplus K_2 \oplus \ldots \oplus
K_2]\).
By taking as \(V(K_{4,\,4}) =
\{\bigcup\limits_{i=1}^2 i_j, 1\leq j\leq 4\}\), the following
set \(\{(2_1, 1_2, 2_2, 1_4; 2_2 1_1), (1_1,
2_1, 1_3, 2_4; 1_3 2_2), (2_1, 1_4, 2_3, 1_1; 2_3 1_3), (2_3, 1_2, 2_4,
1_4; 2_4 1_1)\}\), proves a \(Y_5\)-tree decomposition exists in \(K_{4,\,4}\). Now \(K_{4,\,4} \times K_n\) = \((Y_5 \oplus Y_5 \oplus \ldots \oplus Y_5) \times
(K_2 \oplus K_2 \oplus \ldots \oplus K_2) = (Y_5 \times K_2 ) \oplus
(Y_5 \times K_2 ) \oplus \ldots \oplus (Y_5 \times K_2 )\). A
\(Y_5\)-tree decomposition for \(Y_5 \times K_2\) derives from Lemma 2, which
gives a \(Y_5\)-tree decomposition for
\(K_{4,\,4} \times K_n\).
Lemma 4. \(K_m \times K_n\) admits a \(Y_5\)-tree decomposition for \(m\equiv 0\pmod 4\) and for all \(n\), \(n\geq2\).
Proof. Here, \(m\equiv 0\pmod 4\) can be classified into two cases \((i)\) \(m\equiv 0\pmod 8\) and \((ii)\) \(m\equiv 4\pmod 8\).
Let \(m= 8s, s\geq 1\). Then
\(K_m \times K_n = K_{8s} \times K_n\).
We have a \(Y_5\)-tree decomposition
for \(K_m\), according to the Theorem
1. Then
\(K_{8s} \times K_n = \big[Y_5 \oplus Y_5
\oplus \ldots \oplus Y_5] \times K_n = (Y_5 \times K_n) \oplus (Y_5
\times K_n) \oplus \ldots \oplus (Y_5 \times K_n)\). Lemma 2 which shows
that a \(Y_5 \times K_n\), has a \(Y_5\)-tree decomposition. Thus, we obtain a
\(Y_5\)-tree decomposition for \(K_ {8s} \times K_n\).
Case (ii): Let \(m= 8s+4, s\geq 0\). Then \(K_m \times K_n = K_{8s+4} \times K_n =
\big[(2s+1)K_4 \oplus s(2s+1)K_{4,\,4}\big] \times K_n = (2s+1)[K_4
\times K_n] \oplus s(2s+1)[K_{4,\,4} \times K_n]\). Now, the
Lemmas 1
and 3,
shown that for \(K_4 \times K_n\) and
\(K_{4,\,4} \times K_n\) has a \(Y_5\)-tree decomposition. Thus, we obtain a
\(Y_5\)-tree decomposition for \(K_{8s+1} \times K_n\). From the
aforementioned Cases, we can get a \(Y_5\)-tree decomposition for \(K_m \times K_n\).
Lemma 5. \(K_5 \times K_n\) admits a \(Y_5\)-tree decomposition for all \(n, n\geq2\).
Proof. Now \(K_5 \times K_n = K_5 \times [K_2\oplus K_2 \oplus \ldots \oplus K_2] = (K_5 \times K_2 ) \oplus (K_5 \times K_2 ) \oplus \ldots \oplus (K_5 \times K_2 )\). Let \(V(K_5 \times K_2)= \{\bigcup\limits_{i=1}^5 i_j,\, 1\leq j \leq 2\}\). A \(Y_5\)-tree decomposition can be derives in \(K_5 \times K_2\) as follows: \(\{(1_2, 2_1, 4_2, 5_1; 4_2 3_1), (4_1, 5_2, 3_1, 2_2; 3_1 1_2), (2_1, 5_2, 1_1, 2_2; 1_1 4_2), (2_2, 4_1, 3_2, 1_1; 3_2 2_1),\\ (4_1, 1_2, 5_1, 3_2; 5_1 2_2)\}\). Thus, we obtain a \(Y_5\)-tree decomposition for \(K_5 \times K_n\).
Lemma 6. \(K_{5,\,4} \times K_n\) admits a \(Y_5\)-tree decomposition for all \(n, n\geq2\).
Proof. Let \(K_{5,\,4} \times K_n = K_{5,\,4} \times [K_2\oplus K_2 \oplus \ldots \oplus K_2]\). Let \(V(K_{5,\,4}) = \bigcup \limits_{i=1}^2 V_i\), where \(V_1 = \{1_j \mid 1\leq j \leq 5\}\) and \(V_2 = \{2_j \mid 1\leq j \leq 4\}\). Clearly, the set \(\{(1_1, 2_2, 1_3, 2_3; 1_3 2_4), (2_2, 1_2, 2_3, 1_4; 2_3 1_5), (1_5, 2_4, 1_1, 2_1; 1_1 2_3), (1_2, 2_4, 1_4, 2_2; 1_4 2_1),\\ (2_2, 1_5, 2_1, 1_2; 2_1 1_3)\}\), proves a \(Y_5\)-tree decomposition exists in \(K_{5,\,4}\). Now \(K_{5,\,4} \times K_n\) = \((Y_5 \oplus Y_5 \oplus \ldots \oplus Y_5) \times (K_2 \oplus K_2 \oplus \ldots \oplus K_2) = (Y_5 \times K_2 ) \oplus (Y_5 \times K_2 ) \oplus \ldots \oplus (Y_5 \times K_2 )\). From the Lemma 2, we obtain a \(Y_5\)-tree decomposition in \(Y_5\times K_2\). Thus, we get a \(Y_5\)-tree decomposition for \(K_{5,\,4} \times K_n\).
Lemma 7. \(K_m \times K_n\) admits a \(Y_5\)-tree decomposition for \(m \equiv 1\pmod 4\) and for all \(n\), \(n\geq 2\).
Proof. Here \(m \equiv 1\pmod 4\) can be classified into two Cases \((i)\) \(m \equiv 1\pmod 8\) and \((ii)\) \(m \equiv 5\pmod 8\).
Let \(m= 8s+1, s\geq 1\). Then \(K_m \times K_n = K_{8s+1} \times K_n\). We
have a \(Y_5\)-tree decomposition for
\(K_m\), according to the Theorem 1. Then
\(K_{8s+1} \times K_n = \big[Y_5 \oplus Y_5
\oplus \ldots \oplus Y_5] \times K_n = (Y_5 \times K_n) \oplus (Y_5
\times K_n) \oplus \ldots \oplus (Y_5 \times K_n)\). Now, from
Lemma 2,
which has been shown that a \(Y_5\)-tree decomposition holds for \(Y_5 \times K_n\). Thus, we obtain a \(Y_5\)-tree decomposition for \(K_{8s+1} \times K_n\).
Case (ii): Let \(m= 8s+5, s\geq 0\). Then \(K_m \times K_n = K_{8s+5} \times K_n = \big[ K_5
\oplus 2sK_4 \oplus s(2s-1)K_{4,\,4} \oplus 2sK_{5,\,4}\big] \times K_n
= [K_5 \times K_n] \oplus 2s [K_4 \times K_n] \oplus s(2s-1)[K_{4,\,4}
\times K_n] \oplus 2s[K_{5,\,4} \times K_n]\). Now, the Lemmas 5, 1, 3 and 6, show
that a \(Y_5\)-tree decomposition holds
in \(K_5 \times K_n\), \(K_4 \times K_n\), \(K_{4,\,4} \times K_n\) and \(K_{5,\,4} \times K_n\) respectively. Thus,
we obtain a \(Y_5\)-tree decomposition
for \(K_{8s+5} \times K_n\). From the
aforementioned Cases, we can get a \(Y_5\)-tree decomposition for \(K_m \times K_n\).
Lemma 8. \(K_{4,\,3} \times K_n\) admits a \(Y_5\)-tree decomposition for all \(n, n\geq2\).
Proof. Let \(K_{4,\,3} \times K_n = K_{4,\,3} \times [K_2\oplus K_2 \oplus \ldots \oplus K_2]\). Let \(V(K_{4,\,3}) = \bigcup \limits_{i=1}^2 V_i\), where \(V_1 = \{1_j \mid 1\leq j \leq 4 \}\) and \(V_2 = \{ 2_j \mid 1\leq j\leq 3\}\). Then the following set \(\{(2_2, 1_2, 2_3, 1_1; 2_3 1_3), (2_1, 1_1, 2_2, 1_4; 2_2 1_3), (2_3, 1_4, 2_1, 1_3; 2_1 1_2)\}\) gives a \(Y_5\)-tree decomposition for \(K_{4,\,3}\). Now \(K_{4,\,3} \times K_n\) = \((Y_5 \oplus Y_5 \oplus \ldots \oplus Y_5) \times (K_2 \oplus K_2 \oplus \ldots \oplus K_2) = (Y_5 \times K_2 ) \oplus (Y_5 \times K_2 ) \oplus \ldots \oplus (Y_5 \times K_2 )\). Now, the Lemma 2, has shown that for \(Y_5 \times K_2\) has a \(Y_5\)-tree decomposition. Thus, we obtain a \(Y_5\)-tree decomposition for \(K_{4,\,3} \times K_n\).
Lemma 9. \(Y_5 \times Y_5\) admits a \(Y_5\)-tree decomposition.
Proof. Let us write as \(Y_5 \times Y_5 = Y_5 \times [K_2 \oplus K_2 \oplus K_2 \oplus K_2 ] = (Y_5 \times K_2 ) \oplus (Y_5 \times K_2) \oplus (Y_5 \times K_2) \oplus (Y_5 \times K_2)\). We have a \(Y_5\)-tree decomposition for \(Y_5 \times K_2\), according to the Lemma 2. Thus, we obtain a \(Y_5\)-tree decomposition for \(Y_5 \times Y_5\).
Lemma 10. \(K_m \times K_n\) admits a \(Y_5\)-tree decomposition for \(m \equiv 3 \pmod 4\) and \(n \equiv 0 \pmod 4\).
Proof. Let \(m = 4s+3, s \geq 0\) and \(n = 4t, t \geq 1\). We write \(K_m \times K_n = K_{4s+3} \times K_{4t} = [ sK_4 \oplus K_3 \oplus s K_{4,\,3} \oplus \frac{s(s-1)}{2} K_{4,\,4} ] \times K_{4t} = s[K_4 \times K_{4t}] \oplus [K_3 \times K_{4t}] \oplus s[K_{4,\,3} \times K_{4t}] \oplus \frac{s(s-1)}{2}[ K_{4,\,4} \times K_{4t} ] = s[K_4 \times K_{4t}] \oplus t[K_3 \times K_4] \oplus \frac{t(t-1)}{2}[K_3 \times K_{4,\,4}] \oplus s[K_{4,\,3} \times K_{4t}] \oplus \frac{s(s-1)}{2}[K_{4,\,4} \times K_{4t}]\). Now, the Lemmas 1, 3 and 8 show that a \(Y_5\)-tree decomposition holds in \(K_4 \times K_{4t}, K_3 \times K_4, K_3 \times K_{4,\,4}, K_{4,\,4} \times K_{4t}\) and \(K_{4,\,3} \times K_{4t}\) respectively. Thus, we obtain a \(Y_5\)-tree decomposition for \(K_m \times K_n\).
Lemma 11. \(K_m \times K_n\) admits a \(Y_5\)-tree decomposition for \(m \equiv 3 \pmod 4\) and \(n \equiv 1 \pmod 4\).
Proof. Let \(m = 4s+3, s \geq 0\) and \(n = 4t+1, t \geq 1\). We write \(K_m \times K_n = K_{4s+3} \times K_{4t+1} = \big[ sK_4 \oplus K_3 \oplus sK_{4,\,3} \oplus \frac{s(s-1)}{2}K_{4,\,4}\big] \times \big[ K_5 \oplus (t-1)K_4 \oplus \frac{(t-1)(t-2)}{2}K_{4,\,4} \oplus (t-1)K_{5,\,4}\big] = \big\{s[K_4 \times K_5] \oplus s(t-1)[K_4 \times K_4] \oplus \frac{s(t-1)(t-2)}{2}[K_4 \times K_{4,\,4}] \oplus s(t-1)[K_4 \times K_{5,\,4}]\big\} \oplus \big\{[K_3 \times K_5] \oplus (t-1)[K_3 \times K_4] \oplus \frac{(t-1)(t-2)}{2}[K_3 \times K_{4,\,4}] \oplus (t-1)[K_3 \times K_{5,\,4}]\big\} \oplus \big\{s[K_{4,\,3} \times K_5] \oplus s(t-1)[K_{4,\,3} \times K_4] \oplus \frac{s(t-1)(t-2)}{2}[K_{4,\,3} \times K_{4,\,4}]\oplus s(t-1)[K_{4,\,3} \times K_{5,\,4}]\big\} \oplus \big\{\frac{s(s-1)}{2}[K_{4,\,4} \times K_5] \oplus \frac{s(s-1)(t-1)}{2}[K_{4,\,4} \times K_4] \oplus \frac{s(s-1)(t-1)(t-2)}{4} [K_{4,\,4} \times K_{4,\,4}] \oplus \frac{s(s-1)(t-1)}{2}[K_{4,\,4} \times K_{5,\,4}]\big\}\). Now, the Lemmas 1, 3, 5, 6, 8 and 9 show that a \(Y_5\)-tree decomposition holds in \(K_4 \times K_n, K_{4,\,4} \times K_n, K_5 \times K_n, K_{5,\,4} \times K_n, K_{4,\,3} \times K_n\) and \(Y_5 \times Y_5\) respectively. Thus, we obtain a \(Y_5\)-tree decomposition for \(K_m \times K_n\).
Lemma 12. \(K_{4,\,2} \times K_n\) admits a \(Y_5\)-tree decomposition for all \(n, n\geq2\).
Proof. Let \(K_{4,\,2} \times K_n = K_{4,\,2} \times [K_2\oplus K_2 \oplus \ldots \oplus K_2]\). Let \(V(K_{4,\,2}) = \bigcup \limits_{i=1}^2 V_i\), where \(V_1 = \{ 1_j \mid 1\leq j \leq 4 \}\) and \(V_2 = \{ 2_j \mid 1\leq j \leq 2\}\). Clearly, the set \(\{(2_1, 1_3, 2_2, 1_1; 2_2 1_2), (2_2, 1_4, 2_1, 1_2; 2_1 1_1)\}\), proves a \(Y_5\)-tree decomposition exists in \(K_{4,\,2}\). Now \(K_{4,\,2} \times K_n\) = \((Y_5 \oplus Y_5 \oplus \ldots \oplus Y_5) \times (K_2 \oplus K_2 \oplus \ldots \oplus K_2) = (Y_5 \times K_2 ) \oplus (Y_5 \times K_2 ) \oplus \ldots \oplus (Y_5 \times K_2 )\). Now, the Lemma 2, shows that for \(Y_5\times K_2\) has a \(Y_5\)-tree decomposition. Thus, we obtain a \(Y_5\)-tree decomposition for \(K_{4,\,2} \times K_n\).
Lemma 13. \(K_m \times K_n\) admits a \(Y_5\)-tree decomposition for \(m \equiv 2 \pmod 4\) and \(n \equiv 0 \pmod 4\).
Proof. Let \(m = 4s+2, s\geq 0\) and \(n = 4t, t\geq 1\). We write \(K_m \times K_n = K_{4s+2} \times K_{4t} = [sK_4 \oplus K_2 \oplus \frac{s(s-1)}{2}K_{4,\,4} \oplus sK_{4,\,2}] \times K_{4t} = [sK_4 \oplus K_2 \oplus \frac{s(s-1)}{2}K_{4,\,4} \oplus sK_{4,\,2}] \times [tK_4 \oplus \frac{t(t-1)}{2}K_{4,\,4}] = \big\{st[K_4 \times K_4] \oplus \frac{st(t-1)}{2}[K_4 \times K_{4,\,4}]\big\} \oplus \big\{ t[K_2 \times K_4] \oplus \frac{t(t-1)}{2}[K_2 \times K_{4,\,4}]\big\} \oplus \big\{\frac{s(s-1)t}{2}[K_{4,\,4} \times K_4] \oplus \frac{s(s-1)t(t-1)}{4}[K_{4,\,4} \times K_{4,\,4}]\big\} \oplus \big\{st[K_{4, 2} \times K_4] \oplus \frac{st(t-1)}{2}[K_{4,\,2} \times K_{4,\,4}]\big\}\). Now, the Lemmas 1, 3, 9 and 12 show that a \(Y_5\)-tree decomposition holds in \(K_4 \times K_n, K_{4,\,4} \times K_n, Y_5 \times Y_5\) and \(K_{4,\,2} \times K_n\) respectively. Thus, we obtain a \(Y_5\)-tree decomposition for \(K_m \times K_n\).
Lemma 14. \(K_m \times K_n\) admits a \(Y_5\)-tree decomposition for \(m \equiv 2 \pmod 4\) and \(n \equiv 1 \pmod 4\).
Proof. Let \(m = 4s+2, s\geq 0\) and \(n = 4t+1, t \geq 1\). Then \(K_m \times K_n = K_{4s+2} \times K_{4t+1} = \big[sK_4 \oplus K_2 \oplus \frac{s(s-1)}{2}K_{4,\,4} \oplus s K_{4,\,2}\big] \times \big[K_5 \oplus (t-1)K_4 \oplus \frac{(t-1)(t-2)}{2}K_{4,\,4} \oplus (t-1)K_{5,\,4}\big] = \big\{\{s[K_4 \times K_5] \oplus s(t-1)[K_4 \times K_4] \oplus \frac{s(t-1)(t-2)}{2}[K_4 \times K_{4,\,4}] \oplus s(t-1)[K_4 \times K_{5, 4}]\} \oplus\{[K_2 \times K_5]\oplus (t-1)[K_2 \times K_4] \oplus \frac{(t-1)(t-2)}{2}[K_2 \times K_{4,\,4}] \oplus (t-1)[K_2 \times K_{5,\,4}]\} \oplus \{\frac{s(s-1)}{2}[K_{4,\,4} \times K_5] \oplus \frac{s(s-1)(t-1)}{2}[K_{4,\,4} \times K_4] \oplus \frac{s(s-1)(t-1)(t-2)}{4}[K_{4,\,4} \times K_{4,\,4}] \oplus \frac{s(s-1)(t-1)}{2}[K_{4,\,4} \times K_{5,\,4}]\} \oplus \{s[K_{4,\,2} \times K_5] \oplus s(t-1)[K_{4,\,2} \times K_4] \oplus \frac{s(t-1)(t-2)}{2}[K_{4,\,2} \times K_{4,\,4}] \oplus s(t-1)[K_{4,\,2} \times K_{5,\,4}]\}\big\}\). Now, the Lemmas 1, 3, 5, 6, 9 and 12 show that a \(Y_5\)-tree decomposition holds in \(K_4 \times K_n, K_{4,\,4} \times K_n, K_5 \times K_2, K_{5,\,4} \times K_n, Y_5 \times Y_5\) and \(K_{4,\,2} \times K_n\) respectively. Thus, we obtain a \(Y_5\)-tree decomposition for \(K_m \times K_n\).
Theorem 2. A \(Y_5\)-tree decomposition for \(K_m \times K_n\) holds, if and only if, \(mn(m-1)(n-1) \equiv 0 \pmod 8\).
Proof. One can obtain a necessary condition to find a \(Y_5\)-tree decomposition for \(K_m \times K_n\) as \(mn(m-1)(n-1) \equiv 0 \pmod 8\). From the Lemmas 4, 7, 10, 11, 13 and 14, we can conclude the aforementioned necessary condition is sufficient.
Lemma 15. \(Y_5\times K_n\) admits a gregarious \(Y_5\)-tree decomposition for all \(n\), \(n\geq2\).
Proof. Let us suppose as \(Y_5 \times K_n = Y_5 \times [K_2 \oplus K_2 \oplus \ldots \oplus K_2] = (Y_5 \times K_2) \oplus (Y_5 \times K_2) \oplus \ldots \oplus (Y_5 \times K_2)\). Let \(V(Y_5 \times K_2)= \{\bigcup\limits_{i=1}^5 i_j,\, 1\leq j \leq2\}\). A gregarious \(Y_5\)-tree decomposition can be derives in \(Y_5 \times K_2\) as follows: \(\{(1_1, 2_2, 3_1, 4_2; 3_1 5_2), (1_2, 2_1, 3_2, 4_1; 3_2 5_1)\}\). Thus, we obtain a gregarious \(Y_5\)-tree decomposition for \(Y_5 \times K_n\).
Lemma 16. \(K_ m \times K_n\) admits a gregarious \(Y_5\)-tree decomposition for \(m \equiv 0,1 \pmod 8\) and for all \(n\), \(n\geq 2\).
Proof. Since by Theorem 1, \(Y_5\)-tree decomposition for \(K_m\), \(m = 8s,\, or,\, 8s+1\) exists, let us write as \(K_m \times K_n = \big[Y_5 \oplus Y_5 \oplus \ldots \oplus Y_5\big] \times K_n = \big[Y_5 \times K_n\big]\oplus \big[Y_5 \times K_n\big]\oplus \ldots \oplus \big[Y_5 \times K_n\big]\). Now, the Lemma 15, which shows that \(Y_5 \times K_n\) has a gregarious \(Y_5\)-tree decomposition. Thus, we obtain a gregarious \(Y_5\)-tree decomposition for \(K_m \times K_n\).
Lemma 17. \(K_5 \times K_n\) admits a gregarious \(Y_5\)-tree decomposition for all \(n, n\geq2\).
Proof. Let us suppose as \(K_5 \times K_n = K_5 \times [K_2\oplus K_2 \oplus \ldots \oplus K_2] = (K_5 \times K_2 ) \oplus (K_5 \times K_2 ) \oplus \ldots \oplus (K_5 \times K_2 )\). Let \(V(K_5 \times K_2)= \{\bigcup\limits_{i=1}^5 i_j,\,1\leq j \leq2\}\). A gregarious \(Y_5\)-tree decomposition can be derives in \(K_5 \times K_2\) as follows: \(\{(1_1, 5_2, 2_1, 4_2; 2_1 3_2), (2_1, 1_2, 3_1, 5_2; 3_1 4_2), (3_1, 2_2, 4_1, 1_2; 4_1 5_2), (4_1, 3_2, 5_1, 2_2; 5_1 1_2), \\(5_1, 4_2, 1_1, 3_2; 1_1 2_2)\}\). Thus, we obtain a gregarious \(Y_5\)-tree decomposition for \(K_5 \times K_n\).
Lemma 18. \(K_{8,\,8} \times K_n\) admits a gregarious \(Y_5\)-tree decomposition for all \(n, n\geq2\).
Proof. Let \(V(K_{8,\,8}) = \{\bigcup \limits_{i=1}^2 i_j,\, 1\leq j\leq 8\}\). For \(0 \leq s\leq 1\) and \(1\leq i\leq 8\), \(\kappa_{s}^i = \{1_{i+8s},\, 2_{i+(3s+4)},\, 1_{i+(4s+3)},\, 2_{i+(8s+5)};\, 1_{i+(4s+3)}\,\, 2_{i+(6s+6)}\}\), by taking the residues of \(Z_8\) as \(\{1, 2, 3, \ldots, 8\}\) for subscripts. Let it be clear that, the set \(\{\kappa_{0}^1, \kappa_{1}^1\}\) provides a base block of \(Y_5\)-tree decomposition for \(K_{8,\,8}\). Thus, the collection \(\kappa = \{\kappa_0^i , \kappa_1^i\}, 1\leq i \leq 8\), holds the \(Y_5\)-tree decomposition for \(K_{8,\,8}\). Now we write, \(K_{8,\,8} \times K_n\) = \([Y_5 \oplus Y_5 \oplus \ldots \oplus Y_5] \times K_n = (Y_5 \times K_n ) \oplus (Y_5 \times K_n ) \oplus \ldots \oplus (Y_5 \times K_n )\). Then, the Lemma 15, which shows that \(Y_5 \times K_n\) has a gregarious \(Y_5\)-tree decomposition. Thus, we obtain a gregarious \(Y_5\)-tree decomposition for \(K_{8,\,8} \times K_n\).
Lemma 19. \(K_{8,\,5} \times K_n\) admits a gregarious \(Y_5\)-tree decomposition for all \(n, n\geq2\).
Proof. Let \(V(K_{8,\,5}) =
\bigcup \limits_{i=1}^2 V_i\), where \(V_1 = \{1_j \mid 1\leq j \leq 8 \}\) and
\(V_2 = \{ 2_j \mid 1\leq j\leq 5\}\).
Then the following set gives a \(Y_5\)-tree decomposition for \(K_{8,\,5}\) :
\(\{(2_1, 1_1, 2_3, 1_4; 2_3 1_5), (2_5, 1_8,
2_4, 1_3; 2_4 1_2), (2_5, 1_3, 2_2, 1_1; 2_2 1_4), (1_5, 2_1, 1_6, 2_3;
1_6 2_4), \\ (1_6, 2_5, 1_2, 2_1; 1_2 2_2), (2_1, 1_3, 2_3, 1_7; 2_3
1_2), (2_5, 1_7, 2_4, 1_1; 2_4 1_5), (2_5, 1_5, 2_2, 1_6; 2_2
1_7),\\ (1_1, 2_5, 1_4, 2_4; 1_4 2_1), (1_7, 2_1, 1_8, 2_2; 1_8
2_3)\}\). Let \(K_{8,\,5} \times
K_n\) = \([Y_5 \oplus Y_5
\oplus \ldots \oplus Y_5] \times K_n = (Y_5 \times K_n ) \oplus (Y_5
\times K_n ) \oplus \ldots \oplus (Y_5 \times K_n )\). Now, the
Lemma 15,
which shows that \(Y_5 \times K_n\) has
a gregarious \(Y_5\)-tree
decomposition. Thus, we obtain a gregarious \(Y_5\)-tree decomposition for \(K_{8,\,5}\times K_n\).
Lemma 20. \(K_m \times K_n\) admits a gregarious \(Y_5\)-tree decomposition for \(m \equiv 5 \pmod 8\) and for all \(n\), \(n\geq 2\).
Proof. Let \(m= 8s+5, s\geq 0\). Then \(K_m \times K_n = K_{8s+5} \times K_n = \big[ sK_8 \oplus K_5 \oplus \frac {s(s-1)}{2} K_{8,\,8} \oplus sK_{8,\,5}\big] \times K_n = s[K_8 \times K_n] \oplus [K_5 \times K_n] \oplus \frac{s(s-1)}{2}[K_{8,\,8} \times K_n] \oplus s[K_{8,\,5} \times K_n]\). Now, the Lemmas 16, 17, 18 and 19, show that a gregarious \(Y_5\)-tree decomposition holds in \(K_8 \times K_n\), \(K_5 \times K_n\), \(K_{8,\,8} \times K_n\) and \(K_{8,\,5} \times K_n\) respectively. Thus, we obtain a gregarious \(Y_5\)-tree decomposition for \(K_m \times K_n\).
Lemma 21. \(K_{12} \times K_n\) admits a gregarious \(Y_5\)-tree decomposition.
Proof. Let \(K_{12} \times
K_n\) \(=\) \(\big[ K_5 \oplus (K_{12} \setminus K_5) \big]
\times K_n\) \(=\) \(\big[K_5 \times K_n\big] \oplus \big[(K_{12}
\setminus K_5) \times K_n\big]\). Let \(V(K_{12} \setminus K_5)=\{1, 2, 3, \ldots,
12\}\). Then the following set yields a \(Y_5\)-tree decomposition for \(K_{12} \setminus K_5\):
\(\big\{ (11, 1, 12, 5; 12\,\, 6), (12, 2, 1,
6; 1\,\, 7), (1, 3, 2, 7; 2\, \,8), (2, 4, 3, 8; 3 \,\,9), (3, 5, 4, 9;
4\, \,10), \\(4, 8, 5, 10; 5\, \,11), (1, 4, 12, 7; 12 \,\,3), (6, 5, 1,
8; 1\,\, 9), (3, 6, 2, 9; 2\, \,10), (8, 7, 3, 10; 3 \,\,11), \\ (7, 6,
4, 11; 4\,\, 7), (5, 7, 10, 6; 10\,\, 1), (8, 6, 9, 7; 9 \,\,5), (5, 2,
11, 6; 11\,\, 7) \big\}\).
Therefore, \(K_{12} \times K_n = \big[K_5
\times K_n\big] \oplus \big[ (Y_5 \oplus Y_5 \oplus \ldots \oplus Y_5)
\times K_n \big] = \big[K_5 \times K_n\big] \oplus \big[(Y_5 \times K_n)
\oplus (Y_5 \times K_n) \ldots (Y_5 \times K_n)\big]\). Now, the
Lemmas 15
and 17,
show that a gregarious \(Y_5\)-tree
decomposition holds in \(Y_5\times
K_n\) and \(K_5 \times K_n\)
respectively. Thus, we obtain a gregarious \(Y_5\)-tree decomposition for \(K_{12} \times K_n\).
Lemma 22. \(K_{12,\,8} \times K_n\) admits a gregarious \(Y_5\)-tree decomposition for all \(n, n\geq2\).
Proof. Let \(V(K_{12,\,8}) =
\bigcup \limits_{i = 1}^2 V_i\), where \(V_1 = \{1_j \mid 1\leq j \leq 12 \}\) and
\(V_2 = \{ 2_j \mid 1\leq j\leq 8\}\).
Then the following set gives a \(Y_5\)-tree decomposition of \(K_{12,\,8}\).
\(\big\{(1_7, 2_2, 1_4, 2_8; 1_4 2_5), (1_2,
2_3, 1_5, 2_1; 1_5 2_6), (1_8, 2_7, 1_4, 2_6; 1_4 2_3), (2_8, 1_5, 2_7,
1_{12}; 2_7 1_7), \\ (1_8, 2_8, 1_{11}, 2_7; 1_{11} 2_6), (1_3, 2_1,
1_9, 2_7; 1_9 2_5), (1_8, 2_2, 1_2, 2_4; 1_2 2_6), (1_6, 2_2, 1_1,
2_1; 1_1 2_8), \\ (1_6, 2_8, 1_{12}, 2_5; 1_{12} 2_3), (1_2, 2_8, 1_9,
2_3; 1_9 2_4), (2_1, 1_{11}, 2_3, 1_8; 2_3 1_{10}), (1_9, 2_2, 1_{12},
2_4; 1_{12} 2_1),\\ (1_6, 2_4, 1_{11}, 2_5; 1_{11} 2_2), (1_2, 2_5,
1_5, 2_2; 1_5 2_4), (2_4, 1_7, 2_5, 1_8; 2_5 1_1), (2_4, 1_4, 2_1, 1_6;
2_1 1_2), \\ (1_1, 2_6, 1_8, 2_4; 1_8 2_1), (1_{12}, 2_6, 1_3, 2_4; 1_3
2_2), (1_1, 2_3, 1_7, 2_6; 1_7 2_1), (2_1, 1_{10}, 2_7, 1_2; 2_7 1_1),
\\ (1_1, 2_4, 1_{10}, 2_2; 1_{10} 2_5), (2_8, 1_{10}, 2_6, 1_9; 2_6
1_6), (1_3, 2_5, 1_6, 2_3; 1_6 2_7), (1_7, 2_8, 1_3, 2_3; 1_3
2_7) \big\}\). Now \(K_{12,\,8} \times
K_n\) = \([Y_5 \oplus Y_5
\oplus \ldots \oplus Y_5] \times K_n = (Y_5 \times K_n ) \oplus (Y_5
\times K_n ) \oplus \ldots \oplus (Y_5 \times K_n )\). Now, the
Lemma 15,
which shows that a gregarious \(Y_5\)-tree decomposition holds in \(Y_5 \times K_n\). Thus, \(K_{12,\,8}\times K_n\) has a gregarious
\(Y_5\)-tree decomposition. This
completes the proof.
Lemma 23. \(K_m \times K_n\) admits a gregarious \(Y_5\)-tree decomposition for \(m \equiv 4 \pmod 8\) and for all \(n\), \(n\geq 2\).
Proof. Let \(m= 8s+4, s\geq 1\). Then \(K_m \times K_n = K_{8s+4} \times K_n = \big[ K_{12} \oplus (s-1)K_8 \oplus (s-1)K_{12,\,8} \oplus \frac {(s-2)(s-1)}{2} K_{8,\,8} \big] \times K_n = [K_{12} \times K_n] \oplus [(s-1) K_8 \times K_n] \oplus [(s-1)K_{12,\,8}\times K_n] \oplus \frac{(s-2)(s-1)}{2}[K_{8,\,8} \times K_n]\). Now, the Lemmas 21, 16, 22 and 18, shows that a gregarious \(Y_5\)-tree decomposition holds in \(K_{12} \times K_n\), \(K_8 \times K_n\) ,\(K_{12,\,8} \times K_n\) and \(K_{8,\,8} \times K_n\) respectively. Thus, we obtain a gregarious \(Y_5\)-tree decomposition for \(K_m \times K_n\).
Lemma 24. \(K_6 \times K_4\) admits a gregarious \(Y_5\)-tree decomposition.
Proof. Let \(V(K_6) = \{1, 2, 3,
\ldots 6\}\) and \(V(K_4)= \{1, 2, 3,
4\}\). Then \(V(K_6 \times K_4)=
\bigcup\limits_{i=1}^6 V_i\), \(V_i =
\{i_j \mid 1\leq j \leq 4\}\). Let it be clear that the set given
below yields a gregarious \(Y_5\)-tree
decomposition for \(K_6 \times
K_4\).
\(\big\{ (5_1, 3_2, 1_4, 6_1; 1_4 2_3), (6_4,
4_2, 2_4, 1_1; 2_4 5_2), (1_4, 5_2, 3_4, 2_1; 3_4 4_3), (2_4, 6_2, 4_4,
3_1; 4_4 5_3), \\ (3_4, 1_2, 5_4, 4_1; 5_4 6_3), (4_4, 2_2, 6_4, 5_1;
6_4 1_3), (3_3, 6_1, 1_2, 2_3; 1_2 4_1), (4_3, 1_1, 2_2, 3_3; 2_2 5_1),
\\ (5_3, 2_1, 3_2, 4_1; 3_2 6_1), (6_3, 3_1, 4_2, 5_3; 4_2 1_1), (1_3,
4_1, 5_2, 6_3; 5_2 2_1), (2_3, 5_1, 6_2, 1_3; 6_2 3_1), \\ (5_2, 1_1,
6_3, 3_2; 6_3 2_4), (6_2, 2_1, 1_3, 4_2; 1_3 5_2), (1_2, 3_1, 2_3, 5_4;
2_3 6_2), (2_2, 4_1, 3_3, 6_2; 3_3 1_2), \\ (3_2, 5_4, 4_3, 1_2; 4_3
6_2), (4_2, 6_1, 5_3, 2_2; 5_3 3_2), (1_2, 2_1, 6_4, 5_2; 6_4 3_2),
(2_2, 3_1, 1_4, 6_2; 1_4 4_2), \\ (5_1, 4_3, 2_4, 1_2; 2_4 3_3), (4_2,
5_1, 3_4, 2_2; 3_4 6_2), (3_2, 4_4, 6_1, 5_2; 6_1 1_3), (6_2, 1_1, 5_4,
4_2; 5_4 2_2),\\ (1_1, 6_4, 2_3, 3_4; 2_3 4_2),(2_1, 1_4, 3_3, 6_4; 3_3
5_2), (3_1, 2_4, 4_1, 1_4; 4_1 6_2), (4_3, 6_4, 5_3, 2_4; 5_3 1_2),
\\ (5_1, 4_4, 6_3, 3_4, 6_3 2_2), (6_1, 5_4, 1_3, 4_4; 1_3 3_2), (1_2,
5_1, 2_4, 6_1; 2_4 3_2), (2_2, 6_1, 3_4, 1_1; 3_4 4_2), \\ (3_2, 1_1,
4_4, 2_1; 4_4 5_2), (4_2, 2_1, 5_4, 3_1; 5_4 6_2), (5_2, 3_1, 6_4, 4_1;
6_4 1_2), (5_1, 1_4, 4_3, 3_2; 4_3 2_2),\\ (6_2, 5_3, 3_1, 1_3; 3_1
4_3), (1_2, 6_3, 4_1, 2_3; 4_1 5_3), (2_2, 1_3, 5_1, 3_3, 5_1 6_3),
(4_3, 6_1, 2_3, 3_2; 2_3 5_2), \\ (4_2, 3_3, 1_1, 5_3; 1_1 2_3), (5_2,
4_3, 2_1, 6_3; 2_1 3_3), (4_2, 6_3, 1_4, 5_3; 1_4 2_2), (2_4, 1_3, 3_4,
5_3; 3_4 4_1), \\ (5_4, 3_3, 4_4, 2_3; 4_4 1_2)\big\}\).
Lemma 25. \(K_{8,\,6} \times K_4\) admits a gregarious \(Y_5\)-tree decomposition.
Proof. Let us write as \(V(K_{8,\,6}) = \bigcup \limits_{i=1}^2
V_i\), \(V_1 = \{1_j \mid 1\leq j \leq
8 \}\) and \(V_2 = \{ 2_j \mid 1\leq
j\leq 6\}\). Then the following set gives a \(Y_5\)-tree decomposition of \(K_{8,\,6}\).
\(\big\{(2_6, 1_1, 2_3, 1_4; 2_3 1_5), (2_6,
1_8, 2_4, 1_3; 2_4 1_2), (1_4, 2_6, 1_3, 2_5; 1_3 2_1), (1_5, 2_1, 1_6,
2_3; 1_6 2_4), \\ (1_6, 2_5, 1_2, 2_6; 1_2 2_2), (2_2, 1_3, 2_3, 1_7;
2_3 1_2), (1_5, 2_4, 1_7, 2_6; 1_7 2_5), (1_1, 2_5, 1_4, 2_4; 1_4 2_1),
\\ (1_7, 2_1, 1_8, 2_2; 1_8 2_3), (2_6, 1_6, 2_2, 1_7; 2_2 1_4), (1_8,
2_5, 1_5, 2_2; 1_5 2_6), (1_2, 2_1, 1_1, 2_2; 1_1 2_4)\big\}\).
Then \(K_{8,\,6} \times K_4 = [Y_5 \oplus Y_5
\oplus \ldots \oplus Y_5] \times K_4 =(Y_5 \times K_4) \oplus (Y_5
\times K_4)\oplus \ldots \oplus (Y_5\times K_4)\). A gregarious
\(Y_5\)-tree decomposition for \(Y_5 \times K_4\) derives from Lemma 15, which
provides a gregarious \(Y_5\)-tree
decomposition for \(K_{8,\,6} \times K_
4\).
Lemma 26. \(K_m \times K_n\) admits a gregarious \(Y_5\)-tree decomposition for \(m\equiv 6 \pmod 8\) and \(n=4\).
Proof. Let \(m = 8s+6, s \geq 1\). Then \(K_m \times K_n = K_{8s+6} \times K_4 = \big[ s K_8 \oplus K_6 \oplus \frac{s(s-1)}{2}K_{8,\,8} \oplus sK_{8,\,6}\big] \times K_4 = s[K_8 \times K_4] \oplus [K_6 \times K_4] \oplus \frac{s(s-1)}{2}[K_{8,\,8} \times K_4]\oplus s[K_{8,\,6} \times K_4]\). Now, the Lemmas 16, 18, 24 and 25, show that a gregarious \(Y_5\)-tree decomposition holds in \(K_8 \times K_4\), \(K_{8,\,8} \times K_4\), \(K_6 \times K_4\) and \(K_{8,\,6} \times K_4\) respectively. Thus, we obtain a gregarious \(Y_5\)-tree decomposition for \(K_m \times K_n\).
Lemma 27. \(K_7 \times K_4\) admits a gregarious \(Y_5\)-tree decomposition.
Proof. Let us write as \(K_7
\times K_4 = [K_5 \oplus (K_7\setminus K_5)] \times K_4 = [ K_5 \times
K_4] \oplus [(K_7\setminus K_5) \times K_4]\). By considering
\(V(K_7\setminus K_5) = \{1, 2, 3, \ldots,
7\}\) and \(V(K_4)= \{1, 2, 3,
4\}\), we write as \(V([K_7\setminus
K_5]\times K_4) = \bigcup\limits_{i=1}^7 V_i\), \(V_i = \{i_j \mid 1\leq j \leq 4\}\).
Therefore, the set given below yields a gregarious \(Y_5\)-tree decomposition for \([K_7 \setminus K_5] \times K_4\).
\(\big\{(2_2, 3_3, 1_2, 7_4; 1_2 6_4), (2_3,
3_4, 1_3, 7_1; 1_3 4_2), (2_4, 3_1, 1_4, 7_2; 1_4 6_1), (2_1,3_2, 1_1,
7_3; 1_1 6_3), \\ (1_2, 7_3, 2_4, 5_1; 2_4 6_1), (1_3, 7_4, 2_1, 5_2;
2_1 6_2), (7_1, 1_4, 2_2, 5_3; 2_2 6_3), (1_1, 7_2, 2_3, 5_4; 2_3 6_4),
\\ (7_2, 2_4, 1_1, 6_2; 1_1 3_4), (7_3, 2_1, 1_2, 6_3; 1_2 3_1), (1_3,
3_1, 2_2, 6_4; 2_2 7_4), (3_3, 1_4, 2_3, 6_1; 2_3 7_1),\\ (1_1, 5_3,
2_4, 4_1; 2_4 3_2), (1_2, 5_4, 2_1, 4_2; 2_1 3_4), (1_3, 5_1, 2_2, 4_3;
2_2 7_1), (1_4, 5_2, 2_3, 4_4; 2_3 3_2), \\ (1_1, 5_2, 2_4, 4_3; 2_4
3_3), (1_2, 5_3, 2_1, 4_4; 2_1 7_2), (1_3, 6_1, 2_2, 4_1; 2_2 7_3),
(1_4, 5_1, 2_3, 4_2; 2_3 7_4),\\ (3_4, 2_2, 1_1, 6_4; 1_1 4_2), (3_1,
2_3, 1_2, 6_1; 1_2 4_3), (3_2, 1_3, 2_4, 6_2; 2_4 7_1), (3_3, 2_1, 1_4,
6_2; 1_4 4_1), \\ (2_1, 4_3, 1_1, 5_4; 1_1 3_3), (2_2, 4_4, 1_2, 5_1;
1_2 3_4), (2_3, 4_1, 1_3, 5_2; 1_3 6_4), (2_4, 4_2, 1_4, 5_3; 1_4 3_2),
\\ (5_4, 2_2, 1_3, 4_4; 1_3 6_2), (6_3, 2_4, 1_2, 7_1; 1_2 4_1), (6_4,
2_1, 1_3, 7_2; 1_3 5_4), (2_1, 6_3, 1_4, 7_3; 1_4 4_3),\\ (6_2, 2_3,
1_1, 7_4; 1_1 4_4)\big\}\). Now, the Lemmas 17, which shows that a
gregarious \(Y_5\)-tree decomposition
holds in \(K_5 \times K_4\). Thus, we
obtain a gregarious \(Y_5\)-tree
decomposition for \(K_7 \times
K_4\).
Lemma 28. \(K_{8,\,7} \times K_4\) admits a gregarious \(Y_5\)-tree decomposition.
Proof. Let \(V(K_{8,\,7}) =
\bigcup \limits_{i=1}^2 V_i\), where \(V_1 = \{1_j \mid 1\leq j \leq 8 \}\) and
\(V_2 = \{ 2_j \mid 1\leq j\leq 7\}\).
Then the following set gives a \(Y_5\)-tree decomposition of \(K_{8,\,7}\).
\(\big\{(2_6, 1_1, 2_3, 1_4; 2_3 1_5), (2_6,
1_8, 2_7, 1_3; 2_7 1_2), (1_4, 2_6, 1_3, 2_5; 1_3 2_1), (1_5, 2_1, 1_6,
2_3; 1_6 2_7), \\ (1_6, 2_5, 1_2, 2_6; 1_2 2_2), (2_2, 1_3, 2_3, 1_7;
2_3 1_2), (1_3, 2_4, 1_7, 2_6; 1_7 2_5), (1_2, 2_4, 1_4, 2_5; 1_4 2_1),
\\ (1_7, 2_1, 1_8, 2_2; 1_8 2_3), (2_6, 1_6, 2_2, 1_7; 2_2 1_4), (1_8,
2_5, 1_5, 2_2; 1_5 2_7), (1_2, 2_1, 1_1, 2_2; 1_1 2_4), \\ (2_6, 1_5,
2_4, 1_6; 2_4 1_8), (2_5, 1_1, 2_7, 1_7; 2_7 1_4)\big\}\). Then
\(K_{8,\,7} \times K_4 = [Y_5 \oplus Y_5
\oplus \ldots \oplus Y_5] \times K_4 =(Y_5 \times K_4) \oplus (Y_5
\times K_4)\oplus \ldots \oplus (Y_5\times K_4)\). A gregarious
\(Y_5\)-tree decomposition for \(Y_5 \times K_4\) derives from Lemma 15, which
provides a gregarious \(Y_5\)-tree
decomposition for \(K_{8,\,7} \times
K_4\).
Lemma 29. \(K_m \times K_n\) admits a gregarious \(Y_5\)-tree decomposition for \(m\equiv 7 \pmod 8\) and \(n=4\).
Proof. Let \(m = 8s+7, s \geq 1\). Then \(K_m \times K_n = K_{8s+7} \times K_4 = \big[ s K_8 \oplus K_7 \oplus \frac{s(s-1)}{2}K_{8,\,8} \oplus sK_{8,\,7}\big] \times K_4 = s[K_8 \times K_4] \oplus [K_7 \times K_4] \oplus \frac{s(s-1)}{2}[K_{8,\,8} \times K_4]\oplus s[K_{8,\,7} \times K_4]\). Now, the Lemmas 16, 18, 27 and 28, show that a gregarious \(Y_5\)-tree decomposition holds in \(K_8 \times K_4\), \(K_{8,\,8} \times K_4\), \(K_7 \times K_4\) and \(K_{8,\,7} \times K_4\) respectively. Thus, we obtain a gregarious \(Y_5\)-tree decomposition for \(K_m \times K_n\).
Lemma 30. \(K_{10} \times K_4\) admits a gregarious \(Y_5\)-tree decomposition.
Proof. Let \(K_{10} \times K_4\) \(=\) \(\big[ K_7 \oplus (K_{10} \setminus K_7) \big] \times K_4\) \(=\) \(\big[K_7 \times K_4\big] \oplus \big[(K_{10} \setminus K_7) \times K_4\big]\). Let \(V(K_{10} \setminus K_7) = \{1, 2, 3, \ldots, 10\}\). Clearly, the set \(\big\{ (1, 4, 3, 6; 3\,\, 10), (2, 6, 1, 8; 1\,\,5), (2, 7, 3, 1; 3\, \,8), (7, 1, 2, 4; 2\,\,5), (5, 3, 2, 8; 2\, \,10), \\ (10, 1, 9, 2; 9\,\,3) \big\}\) gives a \(Y_5\)-tree decomposition for \(K_{10} \setminus K_7\). Now \(K_{10} \times K_4 = \big[K_7 \times K_4\big] \oplus \big[ (Y_5 \oplus Y_5 \oplus \ldots \oplus Y_5) \times K_4 \big] = \big[K_7 \times K_4\big] \oplus \big[(Y_5 \times K_4) \oplus (Y_5 \times K_4)\oplus \ldots \oplus(Y_5 \times K_4)\big]\). Now, the Lemmas 15 and 27, which shows that a gregarious \(Y_5\)-tree decomposition holds in \(Y_5\times K_4\) and \(K_7 \times K_4\) respectively. Thus, we obtain a gregarious \(Y_5\)-tree decomposition for \(K_{10} \times K_4\).
Lemma 31. \(K_{10,\,8} \times K_4\) admits a gregarious \(Y_5\)-tree decomposition.
Proof. Let \(V(K_{10,\,8}) =
\bigcup \limits_{i=1}^2 V_i\), where \(V_1 = \{1_j \mid 1\leq j \leq 10 \}\) and
\(V_2 = \{ 2_j \mid 1\leq j\leq 8\}\).
Then the following set gives a \(Y_5\)-tree decomposition for \(K_{10,\,8}\).
\(\big\{(1_7, 2_2, 1_4, 2_8; 1_4 2_5), (1_2,
2_3, 1_5, 2_1; 1_5 2_6), (1_8, 2_7, 1_4, 2_6; 1_4 2_3), (2_8, 1_5, 2_7,
1_{10}; 2_7 1_7), \\ (1_3, 2_1, 1_{10}, 2_2; 1_{10} 2_5), (1_8, 2_2,
1_2, 2_1; 1_2 2_8), (1_6, 2_2, 1_1, 2_1; 1_1 2_8), (1_8, 2_8, 1_{10},
2_3; 1_{10} 2_4), \\ (2_1, 1_6, 2_3, 1_8; 2_3 1_9), (1_2, 2_5, 1_5,
2_2; 1_5 2_4), (2_4, 1_7, 2_5, 1_8; 2_5 1_1), (2_1, 1_4, 2_4, 1_6; 2_4
1_2), \\ (1_{10}, 2_6, 1_8, 2_4; 1_8 2_1), (1_2, 2_6, 1_3, 2_4; 1_3
2_2), (1_1, 2_3, 1_7, 2_6; 1_7 2_1), (2_1, 1_9, 2_7, 1_2; 2_7
1_1),\\ (1_1, 2_4, 1_9, 2_2; 1_9 2_5), (2_8, 1_9, 2_6 1_1; 2_6 1_6),
(1_3, 2_5, 1_6, 2_8; 1_6 2_7), (1_7, 2_8, 1_3, 2_3; 1_3 2_7)
\big\}\). Then \(K_{10,\,8} \times K_4
= [Y_5 \oplus Y_5 \oplus \ldots \oplus Y_5] \times K_4 =(Y_5 \times K_4)
\oplus (Y_5 \times K_4)\oplus \ldots \oplus (Y_5\times K_4)\). A
gregarious \(Y_5\)-tree decomposition
of \(Y_5 \times K_4\) derives from
Lemma 15,
which provides a gregarious \(Y_5\)-tree decomposition for \(K_{10,\,8} \times K_4\).
Lemma 32. \(K_m \times K_n\) admits a gregarious \(Y_5\)-tree decomposition for \(m\equiv 10 \pmod 8\) and \(n=4\).
Proof. Let \(m = 8s+10, s \geq 1\). Then \(K_m \times K_n = K_{8s+10} \times K_4 = \big[ K_{10} \oplus s K_8 \oplus \frac{s(s-1)}{2}K_{8,\,8} \oplus sK_{10,\,8}\big] \times K_4 = [K_{10} \times K_4] \oplus s[K_8 \times K_4] \oplus \frac{s(s-1)}{2}[K_{8,\,8} \times K_4]\oplus s[K_{10,\,8} \times K_4]\). Now, the Lemmas 16, 18, 30 and 31, show that a gregarious \(Y_5\)-tree decomposition holds in \(K_8 \times K_4\), \(K_{8,\,8} \times K_4\), \(K_{10} \times K_4\) and \(K_{10,\,8} \times K_4\) respectively. Thus, we obtain a gregarious \(Y_5\)-tree decomposition for \(K_m \times K_n\).
Lemma 33. \(K_{11} \times K_4\) admits a gregarious \(Y_5\)-tree decomposition.
Proof. Let \(V(K_{11} \setminus K_6) = \{1, 2, 3, \ldots, 11\}\). Clearly the set \(\big\{ (1, 2, 8, 4; 8\,\, 5), (2, 5, 1, 6; 1\,\, 7), (3, 4, 9, 5; 9\, \,2), (2, 3, 1, 8; 1\,\,11), (2, 6, 4, 10; 4\, \,7), \\(5, 6, 3, 8; 3\, \,11), (7, 2, 10, 5; 10\,\, 1), (7, 5, 11, 4; 11\,\,2), (3, 5, 4, 2; 4\,\,1), (1, 9, 3, 7; 3\,\, 10) \big\}\) gives a \(Y_5\)-tree decomposition for \(K_{11} \setminus K_6\). Now \(K_{11} \times K_4 = [(K_{11} \setminus K_6) \oplus K_6 ]\times K_4\) = \([(K_{11} \setminus K_6) \times K_4] \oplus [K_6 \times K_4]\) = \([(Y_5 \oplus Y_5 \oplus \ldots \oplus Y_5)\times K_4] \oplus [K_6 \times K_4] = \big[(Y_5 \times K_4) \oplus (Y_5 \times K_4) \ldots (Y_5 \times K_4)\big] \oplus \big[K_6 \times K_4\big]\). Now, the Lemmas 15 and 24, show that a gregarious \(Y_5\)-tree decomposition holds in \(Y_5\times K_4\) and \(K_6 \times K_4\) respectively. Thus, we obtain a gregarious \(Y_5\)-tree decomposition for \(K_{11} \times K_4\).
Lemma 34. \(K_{11,\,8} \times K_4\) admits a gregarious \(Y_5\)-tree decomposition.
Proof. Let \(V(K_{11,\,8}) =
\bigcup \limits_{i=1}^2 V_i\), where \(V_1 = \{1_j \mid 1\leq j \leq 11 \}\) and
\(V_2 = \{ 2_j \mid 1\leq j\leq 8\}\).
Then the following set gives a \(Y_5\)-tree decomposition for \(K_{11,\,8}\).
\(\big \{(1_7, 2_2, 1_4, 2_8; 1_4 2_5), (1_2,
2_3, 1_5, 2_1; 1_5 2_6), (1_8, 2_7, 1_4, 2_6; 1_4 2_3), (2_8, 1_5, 2_7,
1_{10}; 2_7 1_7), \\ (1_8, 2_8, 1_{11}, 2_7; 1_{11} 2_6), (1_3, 2_1,
1_{10}, 2_2; 1_{10} 2_5), (1_8, 2_2, 1_2, 2_4; 1_2 2_8), (1_6, 2_2, 1_1,
2_1; 1_1 2_8), \\ (1_6, 2_8, 1_{10}, 2_3; 1_{10} 2_4), (2_1, 1_{11},
2_3, 1_8; 2_3 1_9), (1_6, 2_4, 1_{11}, 2_5; 1_{11} 2_2), (1_2, 2_5, 1_5,
2_2; 1_5 2_4), \\ (2_4, 1_7, 2_5, 1_8; 2_5 1_1), (2_4, 1_4, 2_1, 1_6;
2_1 1_2), (1_{10}, 2_6, 1_8, 2_4; 1_8 2_1), (1_2, 2_6, 1_3, 2_4; 1_3
2_2), \\ (1_1, 2_3, 1_7, 2_6; 1_7 2_1), (2_1, 1_9, 2_7, 1_2; 2_7 1_1),
(1_1, 2_4, 1_9, 2_2; 1_9 2_5), (2_8, 1_9, 2_6 1_1; 2_6 1_6),\\ (1_3,
2_5, 1_6, 2_3; 1_6 2_7), (1_7, 2_8, 1_3, 2_3; 1_3 2_7) \big\}\).
Then \(K_{11,\,8} \times K_4 = [Y_5 \oplus Y_5
\oplus \ldots \oplus Y_5] \times K_4 =(Y_5 \times K_4) \oplus (Y_5
\times K_4)\oplus \ldots \oplus (Y_5\times K_4)\). Now, the Lemma
15, which
shows that \(Y_5 \times K_4\) has a
gregarious \(Y_5\)-tree decomposition.
Thus, we obtain a gregarious \(Y_5\)-tree decomposition for \(K_{11,\,8} \times K_4\).
Lemma 35. \(K_m \times K_n\) admits a gregarious \(Y_5\)-tree decomposition for \(m\equiv 11 \pmod 8\) and \(n=4\).
Proof. Let \(m = 8s+11, s \geq 1\). Then \(K_m \times K_n = K_{8s+11} \times K_4 = \big[ K_{11} \oplus s K_8 \oplus \frac{s(s-1)}{2}K_{8,\,8} \oplus sK_{11,\,8}\big] \times K_4 = [K_{11} \times K_4] \oplus s[K_8 \times K_4] \oplus \frac{s(s-1)}{2}[K_{8,\,8} \times K_4]\oplus s[K_{11,\,8} \times K_4]\). Now, the Lemmas 16, 18, 33 and 34, show that a gregarious \(Y_5\)-tree decomposition holds in \(K_8 \times K_4\), \(K_{8,\,8} \times K_4\), \(K_{11} \times K_4\) and \(K_{11,\,8} \times K_4\) respectively. Thus, we obtain a gregarious \(Y_5\)-tree decomposition for \(K_m \times K_n\).
Theorem 3. There exists a gregarious \(Y_5\)-tree decomposition for \(K_m \times K_n\), if and only if, \(mn(m-1)(n-1) \equiv 0 \pmod 8\).
Proof. Necessity: Since \(\mid E(K_m \times K_n)\mid\) \(=\) \(\frac{mn(m-1)(n-1)}{2}\) and \(\mid E(Y_5)\mid = 4\), the required edge
divisibility condition to find a gregarious \(Y_5\)-tree decomposition in \(K_m \times K_n\) is \(\frac{\mid E(K_m \times K_n)\mid}{\mid
E(Y_5)\mid}\) \(=\) \(\frac{mn(m-1)(n-1)}{2 * 4}\). That is,
\(8|mn(m-1)(n-1)\). It can be written
as \(mn(m-1)(n-1) \equiv 0 \pmod
8\).
Sufficiency: Follows from Lemmas 16, 20, 23, 26, 29, 32 and 35.
In this manuscript, we give a complete solution to the problem of finding the existence of a \(Y_5\)-tree (gregarious \(Y_5\)-tree) decomposition in \(K_m \times K_n\). In general, the problem of decomposing \(K_ m \times K_ n\) into \(Y_k\)-tree (gregarious \(Y_ k\)-tree) is yet to solve for \(k \geq 6\).
The authors declare that no funds, grants, or other support were received during the preparation of this manuscript.
The authors have no relavant financial or non-financial interests to disclose.
All authors contributed to the study conception and design. Material preparation, data collection and analysis were performed by S. Gomathi and A. Tamil Elakkiya. The first draft of the manuscript was written by S. Gomathi and all authors commented on previous versions of the manuscript. All authors read and approved the final manuscript.