Gregarious $Y_5$-Tree Decompositions of Tensor Product of  Complete Graphs

Gomathi, S.; Elakkiya, A.

doi:10.61091/jcmcc117-17

Abstract

References

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume 117
Pages: 185-194

Research article

Gregarious $Y_{5}$ -Tree Decompositions of Tensor Product of Complete Graphs

^¹, ^¹

¹PG \& Research Department of Mathematics, Gobi Arts & Science College, Gobichettipalayam-638 453,Tamil Nadu, India.

Received: 27/11/2023
Accepted: 02/12/2023
Published: 11/12/2023

Copyright Link
License

Abstract

$Y_{k}$ -tree is defined as $(v_{1}, v_{2}, \dots, v_{k - 1}; v_{k - 2} v_{k})$ by taking their vertices as $(v_{1}, v_{2}, \dots, v_{k})$ and edges as ${(v_{1} v_{2}, v_{2} v_{3}, \dots, 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 $m n (m - 1) (n - 1) \equiv 0 (\mod 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, $m n (m - 1) (n - 1) \equiv 0 (\mod 8)$ .

Keywords: Decomposition,

Y_{5}

-Tree, Gregarious

Y_{5}

-Tree, Tensor product

1. Introduction

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}, \dots, v_{k - 1}; v_{k - 2} v_{k})$ by taking their vertices as $(v_{1}, v_{2}, \dots, v_{k})$ and edges as ${(v_{1} v_{2}, v_{2} v_{3}, \dots, 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) ∣ p \in V (K_{m}), q \in V (K_{n})}$ and $E (K_{m} \times K_{n}) = {(p, q) (r, s) ∣ p r \in E (K_{m})$ and $q s \in E (K_{n})}$ . Let it be taken as $V (K_{m} \times K_{n}) = {⋃_{i = 1}^{m} i_{j}, 1 \leq j \leq n}$ , by considering $V (K_{m}) = {1, 2, \dots, m}$ and $V (K_{n}) = {1, 2, \dots, 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} ≃ 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 \dots \oplus Y_{5}$ . By applying the distributive properties, we can write as $K_{m} \times K_{n} = [(Y_{5} \oplus Y_{5} \oplus \dots \oplus Y_{5}) \times K_{n}] ≃ [(Y_{5} \times K_{n}) \oplus (Y_{5} \times K_{n}) \oplus \dots \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_{2 m + 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 (\mod 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_{4 m + 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, $m n (m - 1) (n - 1) \equiv 0 (\mod 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, $m n \equiv 0 (\mod 4)$ and $(m - 1) (n - 1) \equiv 0 (\mod 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, $m n (m - 1) (n - 1) \equiv 0 (\mod 8)$ .
$Y_{5}$ -tree decomposition falls on the cases given below:
(i) $m \equiv 0 (\mod 4)$ and for all $n$ , $n \geq 2$ .
(ii) $m \equiv 1 (\mod 4)$ and for all $n$ , $n \geq 2$ .
(iii) $m \equiv 3 (\mod 4)$ and $n \equiv 0 (\mod 4)$ .
(iv) $m \equiv 3 (\mod 4)$ and $n \equiv 1 (\mod 4)$ .
(v) $m \equiv 2 (\mod 4)$ and $n \equiv 0 (\mod 4)$ .
(vi) $m \equiv 2 (\mod 4)$ and $n \equiv 1 (\mod 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 (\mod 8)$ and for all $n$ , $n \geq 2$ .
(ii) $m \equiv 5 (\mod 8)$ and for all $n$ , $n \geq 2$ .
(iii) $m \equiv 4 (\mod 8)$ and for all $n$ , $n \geq 2$ .
(iv) $m \equiv 6 (\mod 8)$ and $n = 4$ .
(v) $m \equiv 7 (\mod 8)$ and $n = 4$ .
(vi) $m \equiv 10 (\mod 8)$ and $n = 4$ .
(vii) $m \equiv 11 (\mod 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 (\mod 8)$ .

2. Decompositions of $K_{m} \times K_{n}$ into $Y_{5}$ Tree

Lemma 1. $K_{4} \times K_{n}$ admits a $Y_{5}$ -tree decomposition for all $n, n \geq 2$ .

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 \dots \oplus K_{2}] = (K_{4} \times K_{2}) \oplus (K_{4} \times K_{2}) \oplus \dots \oplus (K_{4} \times K_{2})$ . By taking as $V (K_{4} \times K_{2}) = {⋃_{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 \geq 2$ .

Proof. As discussed in Lemma 1, we can take $Y_{5} \times K_{n} = Y_{5} \times [K_{2} \oplus K_{2} \oplus \dots \oplus K_{2}] = (Y_{5} \times K_{2}) \oplus (Y_{5} \times K_{2}) \oplus \dots \oplus (Y_{5} \times K_{2})$ . By taking as $V (Y_{5} \times K_{2}) = {⋃_{i = 1}^{5} i_{j}, 1 \leq j \leq 2}$ , 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 \geq 2$ .

Proof. Let us write as $K_{4, 4} \times K_{n} = K_{4, 4} \times [K_{2} \oplus K_{2} \oplus \dots \oplus K_{2}]$ .
By taking as $V (K_{4, 4}) = {⋃_{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 \dots \oplus Y_{5}) \times (K_{2} \oplus K_{2} \oplus \dots \oplus K_{2}) = (Y_{5} \times K_{2}) \oplus (Y_{5} \times K_{2}) \oplus \dots \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 (\mod 4)$ and for all $n$ , $n \geq 2$ .

Proof. Here, $m \equiv 0 (\mod 4)$ can be classified into two cases $(i)$ $m \equiv 0 (\mod 8)$ and $(i i)$ $m \equiv 4 (\mod 8)$ .

Let $m = 8 s, s \geq 1$ . Then $K_{m} \times K_{n} = K_{8 s} \times K_{n}$ . We have a $Y_{5}$ -tree decomposition for $K_{m}$ , according to the Theorem 1. Then $K_{8 s} \times K_{n} = [Y_{5} \oplus Y_{5} \oplus \dots \oplus Y_{5}] \times K_{n} = (Y_{5} \times K_{n}) \oplus (Y_{5} \times K_{n}) \oplus \dots \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_{8 s} \times K_{n}$ .
Case (ii): Let $m = 8 s + 4, s \geq 0$ . Then $K_{m} \times K_{n} = K_{8 s + 4} \times K_{n} = [(2 s + 1) K_{4} \oplus s (2 s + 1) K_{4, 4}] \times K_{n} = (2 s + 1) [K_{4} \times K_{n}] \oplus s (2 s + 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_{8 s + 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 \geq 2$ .

Proof. Now $K_{5} \times K_{n} = K_{5} \times [K_{2} \oplus K_{2} \oplus \dots \oplus K_{2}] = (K_{5} \times K_{2}) \oplus (K_{5} \times K_{2}) \oplus \dots \oplus (K_{5} \times K_{2})$ . Let $V (K_{5} \times K_{2}) = {⋃_{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 \geq 2$ .

Proof. Let $K_{5, 4} \times K_{n} = K_{5, 4} \times [K_{2} \oplus K_{2} \oplus \dots \oplus K_{2}]$ . Let $V (K_{5, 4}) = ⋃_{i = 1}^{2} V_{i}$ , where $V_{1} = {1_{j} ∣ 1 \leq j \leq 5}$ and $V_{2} = {2_{j} ∣ 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 \dots \oplus Y_{5}) \times (K_{2} \oplus K_{2} \oplus \dots \oplus K_{2}) = (Y_{5} \times K_{2}) \oplus (Y_{5} \times K_{2}) \oplus \dots \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 (\mod 4)$ and for all $n$ , $n \geq 2$ .

Proof. Here $m \equiv 1 (\mod 4)$ can be classified into two Cases $(i)$ $m \equiv 1 (\mod 8)$ and $(i i)$ $m \equiv 5 (\mod 8)$ .

Let $m = 8 s + 1, s \geq 1$ . Then $K_{m} \times K_{n} = K_{8 s + 1} \times K_{n}$ . We have a $Y_{5}$ -tree decomposition for $K_{m}$ , according to the Theorem 1. Then $K_{8 s + 1} \times K_{n} = [Y_{5} \oplus Y_{5} \oplus \dots \oplus Y_{5}] \times K_{n} = (Y_{5} \times K_{n}) \oplus (Y_{5} \times K_{n}) \oplus \dots \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_{8 s + 1} \times K_{n}$ .
Case (ii): Let $m = 8 s + 5, s \geq 0$ . Then $K_{m} \times K_{n} = K_{8 s + 5} \times K_{n} = [K_{5} \oplus 2 s K_{4} \oplus s (2 s - 1) K_{4, 4} \oplus 2 s K_{5, 4}] \times K_{n} = [K_{5} \times K_{n}] \oplus 2 s [K_{4} \times K_{n}] \oplus s (2 s - 1) [K_{4, 4} \times K_{n}] \oplus 2 s [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_{8 s + 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 \geq 2$ .

Proof. Let $K_{4, 3} \times K_{n} = K_{4, 3} \times [K_{2} \oplus K_{2} \oplus \dots \oplus K_{2}]$ . Let $V (K_{4, 3}) = ⋃_{i = 1}^{2} V_{i}$ , where $V_{1} = {1_{j} ∣ 1 \leq j \leq 4}$ and $V_{2} = {2_{j} ∣ 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 \dots \oplus Y_{5}) \times (K_{2} \oplus K_{2} \oplus \dots \oplus K_{2}) = (Y_{5} \times K_{2}) \oplus (Y_{5} \times K_{2}) \oplus \dots \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 (\mod 4)$ and $n \equiv 0 (\mod 4)$ .

Proof. Let $m = 4 s + 3, s \geq 0$ and $n = 4 t, t \geq 1$ . We write $K_{m} \times K_{n} = K_{4 s + 3} \times K_{4 t} = [s K_{4} \oplus K_{3} \oplus s K_{4, 3} \oplus \frac{s (s - 1)}{2} K_{4, 4}] \times K_{4 t} = s [K_{4} \times K_{4 t}] \oplus [K_{3} \times K_{4 t}] \oplus s [K_{4, 3} \times K_{4 t}] \oplus \frac{s (s - 1)}{2} [K_{4, 4} \times K_{4 t}] = s [K_{4} \times K_{4 t}] \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_{4 t}] \oplus \frac{s (s - 1)}{2} [K_{4, 4} \times K_{4 t}]$ . Now, the Lemmas 1, 3 and 8 show that a $Y_{5}$ -tree decomposition holds in $K_{4} \times K_{4 t}, K_{3} \times K_{4}, K_{3} \times K_{4, 4}, K_{4, 4} \times K_{4 t}$ and $K_{4, 3} \times K_{4 t}$ 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 (\mod 4)$ and $n \equiv 1 (\mod 4)$ .

Proof. Let $m = 4 s + 3, s \geq 0$ and $n = 4 t + 1, t \geq 1$ . We write $K_{m} \times K_{n} = K_{4 s + 3} \times K_{4 t + 1} = [s K_{4} \oplus K_{3} \oplus s K_{4, 3} \oplus \frac{s (s - 1)}{2} K_{4, 4}] \times [K_{5} \oplus (t - 1) K_{4} \oplus \frac{(t - 1) (t - 2)}{2} K_{4, 4} \oplus (t - 1) K_{5, 4}] = {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_{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}]} \oplus {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}]} \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}]}$ . 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 \geq 2$ .

Proof. Let $K_{4, 2} \times K_{n} = K_{4, 2} \times [K_{2} \oplus K_{2} \oplus \dots \oplus K_{2}]$ . Let $V (K_{4, 2}) = ⋃_{i = 1}^{2} V_{i}$ , where $V_{1} = {1_{j} ∣ 1 \leq j \leq 4}$ and $V_{2} = {2_{j} ∣ 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 \dots \oplus Y_{5}) \times (K_{2} \oplus K_{2} \oplus \dots \oplus K_{2}) = (Y_{5} \times K_{2}) \oplus (Y_{5} \times K_{2}) \oplus \dots \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 (\mod 4)$ and $n \equiv 0 (\mod 4)$ .

Proof. Let $m = 4 s + 2, s \geq 0$ and $n = 4 t, t \geq 1$ . We write $K_{m} \times K_{n} = K_{4 s + 2} \times K_{4 t} = [s K_{4} \oplus K_{2} \oplus \frac{s (s - 1)}{2} K_{4, 4} \oplus s K_{4, 2}] \times K_{4 t} = [s K_{4} \oplus K_{2} \oplus \frac{s (s - 1)}{2} K_{4, 4} \oplus s K_{4, 2}] \times [t K_{4} \oplus \frac{t (t - 1)}{2} K_{4, 4}] = {s t [K_{4} \times K_{4}] \oplus \frac{s t (t - 1)}{2} [K_{4} \times K_{4, 4}]} \oplus {t [K_{2} \times K_{4}] \oplus \frac{t (t - 1)}{2} [K_{2} \times K_{4, 4}]} \oplus {\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}]} \oplus {s t [K_{4, 2} \times K_{4}] \oplus \frac{s t (t - 1)}{2} [K_{4, 2} \times K_{4, 4}]}$ . 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 (\mod 4)$ and $n \equiv 1 (\mod 4)$ .

Proof. Let $m = 4 s + 2, s \geq 0$ and $n = 4 t + 1, t \geq 1$ . Then $K_{m} \times K_{n} = K_{4 s + 2} \times K_{4 t + 1} = [s K_{4} \oplus K_{2} \oplus \frac{s (s - 1)}{2} K_{4, 4} \oplus s K_{4, 2}] \times [K_{5} \oplus (t - 1) K_{4} \oplus \frac{(t - 1) (t - 2)}{2} K_{4, 4} \oplus (t - 1) K_{5, 4}] = {{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}]}}$ . 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, $m n (m - 1) (n - 1) \equiv 0 (\mod 8)$ .

Proof. One can obtain a necessary condition to find a $Y_{5}$ -tree decomposition for $K_{m} \times K_{n}$ as $m n (m - 1) (n - 1) \equiv 0 (\mod 8)$ . From the Lemmas 4, 7, 10, 11, 13 and 14, we can conclude the aforementioned necessary condition is sufficient.

3. Gregarious $Y_{5}$ -tree Decomposition for $K_{m} \times K_{n}$

Lemma 15. $Y_{5} \times K_{n}$ admits a gregarious $Y_{5}$ -tree decomposition for all $n$ , $n \geq 2$ .

Proof. Let us suppose as $Y_{5} \times K_{n} = Y_{5} \times [K_{2} \oplus K_{2} \oplus \dots \oplus K_{2}] = (Y_{5} \times K_{2}) \oplus (Y_{5} \times K_{2}) \oplus \dots \oplus (Y_{5} \times K_{2})$ . Let $V (Y_{5} \times K_{2}) = {⋃_{i = 1}^{5} i_{j}, 1 \leq j \leq 2}$ . 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 (\mod 8)$ and for all $n$ , $n \geq 2$ .

Proof. Since by Theorem 1, $Y_{5}$ -tree decomposition for $K_{m}$ , $m = 8 s, o r, 8 s + 1$ exists, let us write as $K_{m} \times K_{n} = [Y_{5} \oplus Y_{5} \oplus \dots \oplus Y_{5}] \times K_{n} = [Y_{5} \times K_{n}] \oplus [Y_{5} \times K_{n}] \oplus \dots \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_{m} \times K_{n}$ .

Lemma 17. $K_{5} \times K_{n}$ admits a gregarious $Y_{5}$ -tree decomposition for all $n, n \geq 2$ .

Proof. Let us suppose as $K_{5} \times K_{n} = K_{5} \times [K_{2} \oplus K_{2} \oplus \dots \oplus K_{2}] = (K_{5} \times K_{2}) \oplus (K_{5} \times K_{2}) \oplus \dots \oplus (K_{5} \times K_{2})$ . Let $V (K_{5} \times K_{2}) = {⋃_{i = 1}^{5} i_{j}, 1 \leq j \leq 2}$ . 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 \geq 2$ .

Proof. Let $V (K_{8, 8}) = {⋃_{i = 1}^{2} i_{j}, 1 \leq j \leq 8}$ . For $0 \leq s \leq 1$ and $1 \leq i \leq 8$ , $κ_{s}^{i} = {1_{i + 8 s}, 2_{i + (3 s + 4)}, 1_{i + (4 s + 3)}, 2_{i + (8 s + 5)}; 1_{i + (4 s + 3)} 2_{i + (6 s + 6)}}$ , by taking the residues of $Z_{8}$ as ${1, 2, 3, \dots, 8}$ for subscripts. Let it be clear that, the set ${κ_{0}^{1}, κ_{1}^{1}}$ provides a base block of $Y_{5}$ -tree decomposition for $K_{8, 8}$ . Thus, the collection $κ = {κ_{0}^{i}, κ_{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 \dots \oplus Y_{5}] \times K_{n} = (Y_{5} \times K_{n}) \oplus (Y_{5} \times K_{n}) \oplus \dots \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 \geq 2$ .

Proof. Let $V (K_{8, 5}) = ⋃_{i = 1}^{2} V_{i}$ , where $V_{1} = {1_{j} ∣ 1 \leq j \leq 8}$ and $V_{2} = {2_{j} ∣ 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 \dots \oplus Y_{5}] \times K_{n} = (Y_{5} \times K_{n}) \oplus (Y_{5} \times K_{n}) \oplus \dots \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 (\mod 8)$ and for all $n$ , $n \geq 2$ .

Proof. Let $m = 8 s + 5, s \geq 0$ . Then $K_{m} \times K_{n} = K_{8 s + 5} \times K_{n} = [s K_{8} \oplus K_{5} \oplus \frac{s (s - 1)}{2} K_{8, 8} \oplus s K_{8, 5}] \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}$ $=$ $[K_{5} \oplus (K_{12} ∖ K_{5})] \times K_{n}$ $=$ $[K_{5} \times K_{n}] \oplus [(K_{12} ∖ K_{5}) \times K_{n}]$ . Let $V (K_{12} ∖ K_{5}) = {1, 2, 3, \dots, 12}$ . Then the following set yields a $Y_{5}$ -tree decomposition for $K_{12} ∖ K_{5}$ :
${(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)}$ .
Therefore, $K_{12} \times K_{n} = [K_{5} \times K_{n}] \oplus [(Y_{5} \oplus Y_{5} \oplus \dots \oplus Y_{5}) \times K_{n}] = [K_{5} \times K_{n}] \oplus [(Y_{5} \times K_{n}) \oplus (Y_{5} \times K_{n}) \dots (Y_{5} \times K_{n})]$ . 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 \geq 2$ .

Proof. Let $V (K_{12, 8}) = ⋃_{i = 1}^{2} V_{i}$ , where $V_{1} = {1_{j} ∣ 1 \leq j \leq 12}$ and $V_{2} = {2_{j} ∣ 1 \leq j \leq 8}$ . Then the following set gives a $Y_{5}$ -tree decomposition of $K_{12, 8}$ .
${(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})}$ . Now $K_{12, 8} \times K_{n}$ = $[Y_{5} \oplus Y_{5} \oplus \dots \oplus Y_{5}] \times K_{n} = (Y_{5} \times K_{n}) \oplus (Y_{5} \times K_{n}) \oplus \dots \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 (\mod 8)$ and for all $n$ , $n \geq 2$ .

Proof. Let $m = 8 s + 4, s \geq 1$ . Then $K_{m} \times K_{n} = K_{8 s + 4} \times K_{n} = [K_{12} \oplus (s - 1) K_{8} \oplus (s - 1) K_{12, 8} \oplus \frac{(s - 2) (s - 1)}{2} K_{8, 8}] \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, \dots 6}$ and $V (K_{4}) = {1, 2, 3, 4}$ . Then $V (K_{6} \times K_{4}) = ⋃_{i = 1}^{6} V_{i}$ , $V_{i} = {i_{j} ∣ 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}$ .
${(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})}$ .

Lemma 25. $K_{8, 6} \times K_{4}$ admits a gregarious $Y_{5}$ -tree decomposition.

Proof. Let us write as $V (K_{8, 6}) = ⋃_{i = 1}^{2} V_{i}$ , $V_{1} = {1_{j} ∣ 1 \leq j \leq 8}$ and $V_{2} = {2_{j} ∣ 1 \leq j \leq 6}$ . Then the following set gives a $Y_{5}$ -tree decomposition of $K_{8, 6}$ .
${(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})}$ . Then $K_{8, 6} \times K_{4} = [Y_{5} \oplus Y_{5} \oplus \dots \oplus Y_{5}] \times K_{4} = (Y_{5} \times K_{4}) \oplus (Y_{5} \times K_{4}) \oplus \dots \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 (\mod 8)$ and $n = 4$ .

Proof. Let $m = 8 s + 6, s \geq 1$ . Then $K_{m} \times K_{n} = K_{8 s + 6} \times K_{4} = [s K_{8} \oplus K_{6} \oplus \frac{s (s - 1)}{2} K_{8, 8} \oplus s K_{8, 6}] \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} ∖ K_{5})] \times K_{4} = [K_{5} \times K_{4}] \oplus [(K_{7} ∖ K_{5}) \times K_{4}]$ . By considering $V (K_{7} ∖ K_{5}) = {1, 2, 3, \dots, 7}$ and $V (K_{4}) = {1, 2, 3, 4}$ , we write as $V ([K_{7} ∖ K_{5}] \times K_{4}) = ⋃_{i = 1}^{7} V_{i}$ , $V_{i} = {i_{j} ∣ 1 \leq j \leq 4}$ . Therefore, the set given below yields a gregarious $Y_{5}$ -tree decomposition for $[K_{7} ∖ K_{5}] \times K_{4}$ .
${(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})}$ . 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}) = ⋃_{i = 1}^{2} V_{i}$ , where $V_{1} = {1_{j} ∣ 1 \leq j \leq 8}$ and $V_{2} = {2_{j} ∣ 1 \leq j \leq 7}$ . Then the following set gives a $Y_{5}$ -tree decomposition of $K_{8, 7}$ .
${(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})}$ . Then $K_{8, 7} \times K_{4} = [Y_{5} \oplus Y_{5} \oplus \dots \oplus Y_{5}] \times K_{4} = (Y_{5} \times K_{4}) \oplus (Y_{5} \times K_{4}) \oplus \dots \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 (\mod 8)$ and $n = 4$ .

Proof. Let $m = 8 s + 7, s \geq 1$ . Then $K_{m} \times K_{n} = K_{8 s + 7} \times K_{4} = [s K_{8} \oplus K_{7} \oplus \frac{s (s - 1)}{2} K_{8, 8} \oplus s K_{8, 7}] \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}$ $=$ $[K_{7} \oplus (K_{10} ∖ K_{7})] \times K_{4}$ $=$ $[K_{7} \times K_{4}] \oplus [(K_{10} ∖ K_{7}) \times K_{4}]$ . Let $V (K_{10} ∖ K_{7}) = {1, 2, 3, \dots, 10}$ . Clearly, the set ${(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)}$ gives a $Y_{5}$ -tree decomposition for $K_{10} ∖ K_{7}$ . Now $K_{10} \times K_{4} = [K_{7} \times K_{4}] \oplus [(Y_{5} \oplus Y_{5} \oplus \dots \oplus Y_{5}) \times K_{4}] = [K_{7} \times K_{4}] \oplus [(Y_{5} \times K_{4}) \oplus (Y_{5} \times K_{4}) \oplus \dots \oplus (Y_{5} \times K_{4})]$ . 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}) = ⋃_{i = 1}^{2} V_{i}$ , where $V_{1} = {1_{j} ∣ 1 \leq j \leq 10}$ and $V_{2} = {2_{j} ∣ 1 \leq j \leq 8}$ . Then the following set gives a $Y_{5}$ -tree decomposition for $K_{10, 8}$ .
${(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})}$ . Then $K_{10, 8} \times K_{4} = [Y_{5} \oplus Y_{5} \oplus \dots \oplus Y_{5}] \times K_{4} = (Y_{5} \times K_{4}) \oplus (Y_{5} \times K_{4}) \oplus \dots \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 (\mod 8)$ and $n = 4$ .

Proof. Let $m = 8 s + 10, s \geq 1$ . Then $K_{m} \times K_{n} = K_{8 s + 10} \times K_{4} = [K_{10} \oplus s K_{8} \oplus \frac{s (s - 1)}{2} K_{8, 8} \oplus s K_{10, 8}] \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} ∖ K_{6}) = {1, 2, 3, \dots, 11}$ . Clearly the set ${(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)}$ gives a $Y_{5}$ -tree decomposition for $K_{11} ∖ K_{6}$ . Now $K_{11} \times K_{4} = [(K_{11} ∖ K_{6}) \oplus K_{6}] \times K_{4}$ = $[(K_{11} ∖ K_{6}) \times K_{4}] \oplus [K_{6} \times K_{4}]$ = $[(Y_{5} \oplus Y_{5} \oplus \dots \oplus Y_{5}) \times K_{4}] \oplus [K_{6} \times K_{4}] = [(Y_{5} \times K_{4}) \oplus (Y_{5} \times K_{4}) \dots (Y_{5} \times K_{4})] \oplus [K_{6} \times K_{4}]$ . 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}) = ⋃_{i = 1}^{2} V_{i}$ , where $V_{1} = {1_{j} ∣ 1 \leq j \leq 11}$ and $V_{2} = {2_{j} ∣ 1 \leq j \leq 8}$ . Then the following set gives a $Y_{5}$ -tree decomposition for $K_{11, 8}$ .
${(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})}$ . Then $K_{11, 8} \times K_{4} = [Y_{5} \oplus Y_{5} \oplus \dots \oplus Y_{5}] \times K_{4} = (Y_{5} \times K_{4}) \oplus (Y_{5} \times K_{4}) \oplus \dots \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 (\mod 8)$ and $n = 4$ .

Proof. Let $m = 8 s + 11, s \geq 1$ . Then $K_{m} \times K_{n} = K_{8 s + 11} \times K_{4} = [K_{11} \oplus s K_{8} \oplus \frac{s (s - 1)}{2} K_{8, 8} \oplus s K_{11, 8}] \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}$ .

4. Main Result

Theorem 3. There exists a gregarious $Y_{5}$ -tree decomposition for $K_{m} \times K_{n}$ , if and only if, $m n (m - 1) (n - 1) \equiv 0 (\mod 8)$ .

Proof. Necessity: Since $∣ E (K_{m} \times K_{n}) ∣$ $=$ $\frac{m n (m - 1) (n - 1)}{2}$ and $∣ E (Y_{5}) ∣= 4$ , the required edge divisibility condition to find a gregarious $Y_{5}$ -tree decomposition in $K_{m} \times K_{n}$ is $\frac{∣ E (K_{m} \times K_{n}) ∣}{∣ E (Y_{5}) ∣}$ $=$ $\frac{m n (m - 1) (n - 1)}{2 * 4}$ . That is, $8 | m n (m - 1) (n - 1)$ . It can be written as $m n (m - 1) (n - 1) \equiv 0 (\mod 8)$ .
Sufficiency: Follows from Lemmas 16, 20, 23, 26, 29, 32 and 35.

5. Conclusion

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

Funding Information

The authors declare that no funds, grants, or other support were received during the preparation of this manuscript.

Conflict of Interest

The authors have no relavant financial or non-financial interests to disclose.

Author Contributions

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.

References:

Ringel, Problem 25, In Theory of Graphs and its applications, In: Proceeding of the Symposium Smolenice, $(1963)\,p. 162$. [Google Scholor]
Huang, C. and Rosa, A., 1978. Decomposition of complete graphs into trees. Ars combinatoria, 5, pp.23-63. [Google Scholor]
Bermond, J.C., Huang, C., Rosa, A. and Sotteau, D., 1980. Decomposition of complete graphs into isomorphic subgraphs with five vertices. Ars combinatoria, 10, pp.211-254. [Google Scholor]
Sethuraman, G. and Murugan, V., 2021. Decomposition of Complete Graphs into Arbitrary Trees. Graphs and Combinatorics, 37(4), pp.1191-1203. [Google Scholor]
Drmota, M. and Llado, A., 2014. Almost every tree with m edges decomposes K2m, 2m. Combinatorics, Probability and Computing, 23(1), pp.50-65. [Google Scholor]
Haggard, G. and McWha, P., 1975. Decomposition of complete graphs into trees. Czechoslovak Mathematical Journal, 25(1), pp.31-36. [Google Scholor]
Barat, J. and Gerbner, D., 2012. Edge-decomposition of graphs into copies of a tree with four edges. arXiv preprint arXiv:1203.1671. [Google Scholor]
Jao, K.F., Kostochka, A.V. and West, D.B., 2013. Decomposition of Cartesian products of regular graphs into isomorphic trees. Journal of Combinatorics, 4(4), pp.469-490. [Google Scholor]
{MSJ}Truszczynski, M., 1991. Decompositions of regular bipartite graphs. Discrete Mathematics, 89, pp.57-27. [Google Scholor]
Llado, A., Lopez, S.C. and Moragas, J., 2010. Every tree is a large subtree of a tree that decomposes Kn or Kn, n. Discrete mathematics, 310(4), pp.838-842. [Google Scholor]
Montgomery, R., Pokrovskiy, A. and Sudakov, B., 2021. A proof of Ringel’s conjecture. Geometric and Functional Analysis, 31(3), pp.663-720. [Google Scholor]
Elakkiya, A.T. and Muthusamy, A., 2016. Gregarious kite decomposition of tensor product of complete graphs. Electronic Notes in Discrete Mathematics, 53, pp.83-96. [Google Scholor]
Elakkiya, A.T. and Muthusamy, A., 2020. Gregarious kite factorization of tensor product of complete graphs. Discussiones Mathematicae Graph Theory, 40(1), pp.7-24. [Google Scholor]

[1] Ringel, Problem 25, In Theory of Graphs and its applications, In: Proceeding of the Symposium Smolenice, $(1963)\,p. 162$. [Google Scholor]

[2] Huang, C. and Rosa, A., 1978. Decomposition of complete graphs into trees. Ars combinatoria, 5, pp.23-63. [Google Scholor]

[3] Bermond, J.C., Huang, C., Rosa, A. and Sotteau, D., 1980. Decomposition of complete graphs into isomorphic subgraphs with five vertices. Ars combinatoria, 10, pp.211-254. [Google Scholor]

[4] Sethuraman, G. and Murugan, V., 2021. Decomposition of Complete Graphs into Arbitrary Trees. Graphs and Combinatorics, 37(4), pp.1191-1203. [Google Scholor]

[5] Drmota, M. and Llado, A., 2014. Almost every tree with m edges decomposes K2m, 2m. Combinatorics, Probability and Computing, 23(1), pp.50-65. [Google Scholor]

[6] Haggard, G. and McWha, P., 1975. Decomposition of complete graphs into trees. Czechoslovak Mathematical Journal, 25(1), pp.31-36. [Google Scholor]

[7] Barat, J. and Gerbner, D., 2012. Edge-decomposition of graphs into copies of a tree with four edges. arXiv preprint arXiv:1203.1671. [Google Scholor]

[8] Jao, K.F., Kostochka, A.V. and West, D.B., 2013. Decomposition of Cartesian products of regular graphs into isomorphic trees. Journal of Combinatorics, 4(4), pp.469-490. [Google Scholor]

[9] {MSJ}Truszczynski, M., 1991. Decompositions of regular bipartite graphs. Discrete Mathematics, 89, pp.57-27. [Google Scholor]

[10] Llado, A., Lopez, S.C. and Moragas, J., 2010. Every tree is a large subtree of a tree that decomposes Kn or Kn, n. Discrete mathematics, 310(4), pp.838-842. [Google Scholor]

[11] Montgomery, R., Pokrovskiy, A. and Sudakov, B., 2021. A proof of Ringel’s conjecture. Geometric and Functional Analysis, 31(3), pp.663-720. [Google Scholor]

[12] Elakkiya, A.T. and Muthusamy, A., 2016. Gregarious kite decomposition of tensor product of complete graphs. Electronic Notes in Discrete Mathematics, 53, pp.83-96. [Google Scholor]

[13] Elakkiya, A.T. and Muthusamy, A., 2020. Gregarious kite factorization of tensor product of complete graphs. Discussiones Mathematicae Graph Theory, 40(1), pp.7-24. [Google Scholor]

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

Gregarious $Y_{5}$ -Tree Decompositions of Tensor Product of Complete Graphs

Abstract

1. Introduction

2. Decompositions of $K_{m} \times K_{n}$ into $Y_{5}$ Tree

3. Gregarious $Y_{5}$ -tree Decomposition for $K_{m} \times K_{n}$

4. Main Result

5. Conclusion

Funding Information

Conflict of Interest

Author Contributions

References:

Information

Guidelines

CP Initiatives

Follow CP

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

Gregarious Y5-Tree Decompositions of Tensor Product of Complete Graphs

Abstract

1. Introduction

2. Decompositions of Km×Kn into Y5 Tree

3. Gregarious Y5-tree Decomposition for Km×Kn

4. Main Result

5. Conclusion

Funding Information

Conflict of Interest

Author Contributions

References:

Information

Guidelines

CP Initiatives

Follow CP

Gregarious $Y_{5}$ -Tree Decompositions of Tensor Product of Complete Graphs

2. Decompositions of $K_{m} \times K_{n}$ into $Y_{5}$ Tree

3. Gregarious $Y_{5}$ -tree Decomposition for $K_{m} \times K_{n}$