Decomposition of a complete  equipartite graph into gregarious $\mathcal{Y}_5$ Tree

Gomathi, S.; Elakkiya, A. Tamil

doi:10.61091/jcmcc123-01

Abstract

1. Introduction
2. Gregarious Y5 tree decomposition of Km(n)
3. Conclusion

References

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume 123
Pages: 3-19

Research article

Decomposition of a complete equipartite graph into gregarious $Y_{5}$ Tree

^¹, ^¹

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

Received: 02/10/2024
Accepted: 05/12/2024
Published: 31/12/2024

Copyright Link
License

Abstract

A $Y$ tree on $k$ vertices is denoted by $Y_{k}$ . To decompose a graph into $Y_{k}$ trees, it is necessary to create a collection of subgraphs that are isomorphic to $Y_{k}$ tree and are all distinct. It is possible to acquire the necessary condition to decompose $K_{m} (n)$ into $Y_{k}$ trees ( $k \geq 5$ ), which has been obtained as $n^{2} m (m - 1) \equiv 0 (\mod 2 (k - 1))$ . It has been demonstrated in this document that, a gregarious $Y_{5}$ tree decomposition in $K_{m} (n)$ is possible only if $n^{2} m (m - 1) \equiv 0 (\mod 8)$ .

Keywords: Decomposition, Complete equipartite graph,

Y_{5}

tree, Gregarious

Y_{5}

tree

1. Introduction

To create a $Y_{k}$ tree $(v_{1} v_{2} \dots v_{k - 1}; v_{k - 2} v_{k})$ , its edges are represented as ${(v_{1} v_{2}, v_{2} v_{3}, \dots, v_{k - 2} v_{k - 1}) \cup (v_{k - 2} v_{k})}$ while the vertices are represented as ${v_{1}, v_{2}, \dots, v_{k}}$ . A $Y_{5}$ tree $(v_{1} v_{2} v_{3} v_{4}; v_{3} v_{5})$ can be seen in Figure 1.

The wreath product $(G \otimes H)$ of $G$ and $H$ be defined in this way: $V (G \otimes H)$ $=$ ${(u, v) ∣ u \in V (G), v \in V (H)}$ and $E (G \otimes H)$ $=$ ${(u, v) (x, y) ∣ u = x$ and $v y \in E (H)$ , or $u x \in E (G)}$ . $I_{r}$ is the term used to describe the set of $r$ vertices. The extended graph ( $G \otimes I_{r}$ ) of G is also a multipartite graph which is described in the following manner: $V (G \otimes I_{r})$ $=$ ${p_{q} ∣ p \in V (G), q \in I_{r}}$ and $E (G \otimes I_{r})$ $=$ ${p_{q} s_{t} ∣ p s \in E (G)$ and $q, t \in I_{r}}$ . To make it easier for us, the extented graph is denoted by $E_{r} (G)$ . Here $K_{m} \otimes I_{n}$ is referred as the complete equipartite graph and is also identified by $K_{m} (n)$ . Here, the extended graph $E_{r} (K_{m} (n))$ can be considered as the extended graph $E_{n r} (K_{m})$ , ie., $K_{m} (n r)$ .

Decomposition of a graph $G$ can be partitioned into subgraphs ${G_{i}, 1 \leq i \leq n}$ , where each $G_{i}$ is distinct by its edges, in addition with, the edge set of $G$ is the union of the edge set of all subgraphs. In such a case that, if there is an isomorphism between each subgraph $G_{i}$ and a graph $H$ , then $G$ is said to decompose into $H$ .

However, a $Y_{5}$ tree decomposition in $E_{r} (G)$ is termed as gregarious, if for every $Y_{5}$ tree, all its vertices are assigned to various partite sets.

Numerous authors have investigated tree decompositions and their special characteristic, in particular gregarious tree decompositions. C. Huang and A. Rosa [10] demonstrated that the complete graph $K_{m}$ admits a $Y_{5}$ tree decomposition when $m \equiv 0, 1 (\mod 8)$ . The study of $G$ -decomposition of complete graphs, with $G$ having $5$ vertices, is detailed in [2]. According to the conjecture by Ringel [16], it is proposed that $K_{2 m + 1}$ has been decomposed into a tree with precisely $m$ edges. $J a^{^{'}} n o s$ $B a r a^{^{'}} t$ and $D a^{^{'}} n i e l$ $G e r b n e r$ [1] show that 191-edge connected graph admits a $Y$ tree decomposition. To know more about tree decompositions, refer [3,4,17,14,9,12,11,13,15]. A gregarious kite decomposition in $K_{m} \times K_{n}$ is demonstrated to exist by A. Tamil Elakkiya and A. Muthusamy [5], with the condition that $m n (m - 1) (n - 1) \equiv 0 (\mod 8)$ being necessary and sufficient, where $\times$ denotes tensor product of graph. In [6], A. Tamil Elakkiya and A. Muthusamy established the conditions for a gregarious kite factorization of $K_{m} \times K_{n}$ , stating that this factorization is only possible when $m n \equiv 0 (\mod 4)$ and $(m - 1) (n - 1) \equiv 0 (\mod 2)$ are present. A kite decomposition for $K_{m} (n)$ is gregarious is not possible unless $m \equiv 0, 1 (\mod 8)$ for odd $n$ and $m \geq 4$ for even $n$ are present, which has been investigated in [7]. In [8], S. Gomathi and A. Tamil Elakkiya established the conditions of a gregarious $Y_{5}$ tree decomposition for $K_{m} \times K_{n}$ , stating that this decomposition exists only if $m n (m - 1) (n - 1) \equiv 0 (\mod 8)$ is present.

Our main concern is, to decompose a complete equipartite graph as gregarious $Y_{5}$ trees. This paper proves that a gregarious $Y_{5}$ tree decomposition for $K_{m} (n)$ is only possible if $n^{2} m (m - 1) \equiv 0 (\mod 8)$ . By the notion of a gregarious $Y_{5}$ tree decomposition, the number of partite sets must be at least $5 (m \geq 5)$ . Moreover, a gregarious $Y_{5}$ tree decomposition for $K_{m} (n)$ falls on the following cases:

$m \equiv 0, 1 (\mod 8)$ , for all $n$ , $n \geq 2$ .
$m \equiv 5, 6, 7, 10, 11, 12 (\mod 8)$ , for even $n$ .

To establish our key result, the following result is necessary:

Theorem 1.1. [10] For

m \equiv 0, 1 (\mod 8)

, a

Y_{5}

tree decomposition is possible in

K_{m}

2. Gregarious $Y_{5}$ tree decomposition of $K_{m} (n)$

Remark 2.1. A Latin square of order

r

, denoted as

L = (a_{i j})

, is an

r \times r

array where every row and every column contains only the elements

{1, 2, 3, \dots, r}

once, in which each cell

a_{i j}

would satisfies the arithmetic operation such as

a_{i j} = i + j - 1 (\mod r)

. If

a_{i j} = a_{(i + h) (j + k)}

and

a_{i (j + k)} = a_{(i + h) j}

, then the set

{a_{i j}, a_{i (j + k)}, a_{(i + h) j}, a_{(i + h) (j + k)}}

is called as

Y

tree cell. Here

h

and

k

are integers, which are equal to

\frac{r}{2}

r

is even. It provides the following three disjoint

Y_{5}

trees:

(i) $(1_{i + h} 2_{j + k} 1_{i} 3_{a_{(i + h) (j + k)}}; 1_{i} 2_{j})$

(ii) $(2_{j + k} 3_{a_{(i + h) (j + k)}} 1_{i + h} 2_{j}; 1_{i + h} 3_{a_{i (j + k)}})$

(iii) $(3_{a_{i j}} 2_{j} 3_{a_{(i + h) j}} 2_{j + k}; 3_{a_{(i + h) j}} 1_{i})$ ,

where the subscripts are considered to be divisible by $r$ and their remainders must be taken as $1, 2, 3, \dots, r$ .

For example, let us consider the Latin square of order $4$ as given in Table 1.

Table 1 Latin square of order $4$ ( $L_{4}$ )
$1$	2	$3$	4
2	3	4	1
$3$	4	$1$	2
4	1	2	3

Here $h, k = 2$ , and $i, j = 1$ , so we get $a_{11} = a_{33}$ and $a_{13} = a_{31}$ . Now, the $Y$ tree cell $(a_{11}, a_{13}, a_{31}, a_{33})$ gives the following: $(1_{3} 2_{3} 1_{1} 3_{a_{33}}; 1_{1} 2_{1})$ , $(2_{3} 3_{a_{33}} 1_{3} 2_{1}; 1_{3} 3_{a_{13}})$ and $(3_{a_{11}} 2_{1} 3_{a_{31}} 2_{3}; 3_{a_{31}} 1_{1})$ . Then $a_{11} = a_{33} = 1$ and $a_{13} = a_{31} = 3$ implies the disjoint $Y_{5}$ trees $(1_{3} 2_{3} 1_{1} 3_{1}; 1_{1} 2_{1})$ , $(2_{3} 3_{1} 1_{3} 2_{1}; 1_{3} 3_{3})$ and $(3_{1} 2_{1} 3_{3} 2_{3}; 3_{3} 1_{1})$ .

Lemma 2.2. For any

Y_{5}

tree, there is a gregarious

Y_{5}

tree decomposition for

E_{r} (Y_{5})

r \geq 2

Proof. By taking $V (E_{r} (Y_{5}))$ $=$ ${⋃_{p = 1}^{5} p_{q}, 1 \leq q \leq r}$ and by using the latin square $L$ of order $r$ , the set ${1_{i} 2_{j} 3_{a_{i j}} 4_{i}; 3_{a_{i j}} 5_{j}}, 1 \leq i, j \leq r$ , $r \geq 2$ , provides a gregarious $Y_{5}$ tree decomposition for $E_{r} (Y_{5})$ .

Lemma 2.3. A gregarious

Y_{5}

tree decomposition is admissible in

E_{r} (H)

r \geq 2

, if a

Y_{5}

tree decomposition is possible in

H

Proof. If there is a collection $S$ of $Y_{5}$ trees in the decomposition of $H$ , then by applying Lemma 2.2 to each $Y_{5} \in S$ , we will get a gregarious $Y_{5}$ tree decomposition for $E_{r} (Y_{5})$ . Consequently, we can attain a gregarious $Y_{5}$ tree decomposition for $E_{r} (H)$ , $r \geq 2$ .

Lemma 2.4. A gregarious

Y_{5}

tree decomposition is admissible in

K_{m} (n)

, when

m \equiv 0, 1 (\mod 8)

and for every

n

n \geq 2

Proof. In Theorem 1.1, stating that, $Y_{5}$ tree decomposition is possible for $K_{m}$ when $m \equiv 0, 1 (\mod 8)$ . Thus, according to the Lemma 2.3, we can attain a gregarious $Y_{5}$ tree decomposition for $E_{r} (K_{m})$ , $r \geq 2$ .

Lemma 2.5. A gregarious

Y_{5}

tree decomposition for each graph

G

\in

G

=

{K_{6, 6, 6}, K_{8, 8, 8}, K_{10, 10, 10},

K_{12, 12, 12}}

is admissible in

E_{2} (G)

Proof. Let us consider $V (K_{2, 2, 2}) = {⋃_{p = 1}^{3} p_{q}, 1 \leq q \leq 2}$ . The set given below contains a $Y_{5}$ tree decomposition for $K_{2, 2, 2} : {(3_{2} 1_{2} 3_{1} 1_{1}; 3_{1} 2_{1}), (2_{2} 3_{2} 2_{1} 1_{1}; 2_{1} 1_{2}), (3_{2} 1_{1} 2_{2} 1_{2}; 2_{2} 3_{1})}$ . Consequently, we may derive a gregarious $Y_{5}$ tree decomposition for $E_{r} (K_{2, 2, 2})$ if $r = 3, 4, 5, 6$ , according to the Lemma 2.3. That is, a gregarious $Y_{5}$ tree decomposition exists for the graphs $G$ $=$ ${K_{6, 6, 6}, K_{8, 8, 8}, K_{10, 10, 10}, K_{12, 12, 12}}$ , since $E_{r} (K_{m} (n))$ $≃$ $K_{m} (n r)$ . Moreover, by repeating the same process to each graph $G$ $\in$ $G$ , we can acquire a gregarious $Y_{5}$ tree decomposition for $E_{2} (G)$ .

Lemma 2.6. A gregarious

Y_{5}

tree decomposition for each graph

G

\in

G

=

{K_{8, 8, 5}

K_{8, 8, 6}

K_{8, 8, 7}}

is admissible in

E_{2} (G)

Proof. (1) A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{8, 8, 5})$ can be derived as follows:
Let $V (K_{8, 8, 5})$ $=$ ${(⋃_{p = 1}^{2} p_{q}, 1 \leq q \leq 8) \cup (3_{q}, 1 \leq q \leq 5)}$ . By removing the entiries 6, 7 and 8 from Table 2, we can attain a latin square $L$ in Table 3. By using Table 3, we can produce a set $S_{1}$ of $Y_{5}$ tree decomposition for $K_{8, 8, 5}$ as follows:

Table 2 Latin square of order $8$ ( $L_{8}$ )
1	2	3	4	5	6	7	8
2	3	4	5	6	7	8	1
3	4	5	6	7	8	1	2
4	5	6	7	8	1	2	3
5	6	7	8	1	2	3	4
6	7	8	1	2	3	4	5
7	8	1	2	3	4	5	6
8	1	2	3	4	5	6	7

Table 3 Dropped the entries $6, 7, 8$ from $L_{8}$
1	2	3	4	5	$\times$	$\times$	$\times$
2	3	4	5	$\times$	$\times$	$\times$	1
3	4	5	$\times$	$\times$	$\times$	1	2
4	5	$\times$	$\times$	$\times$	1	2	3
5	$\times$	$\times$	$\times$	1	2	3	4
$\times$	$\times$	$\times$	1	2	3	4	5
$\times$	$\times$	1	2	3	4	5	$\times$
$\times$	1	2	3	4	5	$\times$	$\times$

$∙$ As discussed in Remark 2.1, if $a_{i j} = a_{(i + h) (j + k)} = 5$ and $a_{i (j + k)} = a_{(i + h) j} = 1$ , we get the following $Y$ tree cells ${(a_{15}, a_{11}, a_{55}, a_{51}), (a_{24}, a_{28}, a_{64}, a_{68}), (a_{33}, a_{37}, a_{73}, a_{77}), (a_{42}, a_{46}, a_{82}, a_{86})}$ . It follows that these $Y$ tree cells yield $12$ copies of $Y_{5}$ trees, in which each are isomorphic and disjoint mutually.

$∙$ For all $(i, j) \in {(1, 2), (2, 1), (3, 8), (4, 7), (5, 6), (6, 5), (7, 4), (8, 3)}$ , we have $a_{i j} = 2$ and for all $(i, j) \in {(1, 3), (2, 2), (3, 1), (4, 8), (5, 7), (6, 6), (7, 5), (8, 4)}$ , we have $a_{i j} = 3$ . It is possible to obtain a $Y_{5}$ tree corresponding to each $(i, j)$ , such as $(3_{a_{i j}} 2_{j} 1_{i} 2_{k + 6 - i}; 1_{i} 3_{k + 1})$ , if $a_{i j} = k$ , $k = 2, 3$ . Thus we may include these $16$ disjoint copies of $Y_{5}$ trees in $S_{1}$ .

$∙$ Similarly, for all $(i, j) \in {(1, 4), (2, 3), (3, 2), (4, 1), (5, 8), (6, 7), (7, 6), (8, 5)}$ , $a_{i j} = k$ , $k = 4$ , it is possible to obtain a $Y_{5}$ tree. We then place the $8$ disjoint copies of $Y_{5}$ trees follows from $(3_{a_{i j}} 2_{j} 1_{i} 2_{j + 2}; 1_{i} 3_{k - 2})$ in $S_{1}$ . All together implies a $Y_{5}$ tree decomposition for $K_{8, 8, 5}$ . As a consequence of it, a gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{8, 8, 5})$ may derived through the use of Lemma 2.3.

(2) A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{8, 8, 6})$ can be derived as follows:
Let $V (K_{8, 8, 6})$ $=$ ${(⋃_{p = 1}^{2} p_{q}, 1 \leq q \leq 8) \cup (3_{q}, 1 \leq q \leq 6)}$ . By removing the entiries 7 and 8 from Table 2, we can attain a latin square $L$ in Table 4. By using Table 4, we can produce a set $S_{2}$ of $Y_{5}$ tree decomposition for $K_{8, 8, 6}$ as follows:

Table 4 Dropped the entries $7, 8$ from $L_{8}$
1	2	3	4	5	6	$\times$	$\times$
2	3	4	5	6	$\times$	$\times$	1
3	4	5	6	$\times$	$\times$	1	2
4	5	6	$\times$	$\times$	1	2	3
5	6	$\times$	$\times$	1	2	3	4
6	$\times$	$\times$	1	2	3	4	5
$\times$	$\times$	1	2	3	4	5	6
$\times$	1	2	3	4	5	6	$\times$

$∙$ As discussed in Remark 2.1, if $a_{i j} = a_{(i + h) (j + k)} = 5$ and $a_{i (j + k)} = a_{(i + h) j} = 1$ , we get the following $Y$ tree cells ${(a_{15}, a_{11}, a_{55}, a_{51}), (a_{24}, a_{28}, a_{64}, a_{68}), (a_{33}, a_{37}, a_{73}, a_{77}), (a_{42}, a_{46}, a_{82}, a_{86})}$ . It follows that the $Y$ tree cells yield $12$ copies of $Y_{5}$ trees, in which each are isomorphic and disjoint mutually.

$∙$ As discussed in Remark 2.1, if $a_{i j} = a_{(i + h) (j + k)} = 2$ and $a_{i (j + k)} = a_{(i + h) j} = 6$ , we get the following $Y$ tree cells ${(a_{12}, a_{16}, a_{52}, a_{56}), (a_{21}, a_{25}, a_{61}, a_{65}), (a_{38}, a_{34}, a_{78}, a_{74}), (a_{47}, a_{43}, a_{87}, a_{83})}$ . It follows that the $Y$ tree cells yield $12$ copies of $Y_{5}$ trees.

$∙$ For all $(i, j) \in {(1, 3), (2, 2), (3, 1), (4, 8), (5, 7), (6, 6), (7, 5), (8, 4)}$ , $a_{i j} = k$ , $k = 3$ , it is possible to obtain a $Y_{5}$ tree. We then place the $8$ copies of $Y_{5}$ trees follows from $(3_{a_{i j}} 2_{j} 1_{i} 2_{k + 6 - i}; 1_{i} 3_{k + 1})$ in $S_{2}$ .

$∙$ For all $(i, j) \in {(1, 4), (2, 3), (3, 2), (4, 1), (5, 8), (6, 7), (7, 6), (8, 5)}$ , $a_{i j} = k$ , $k = 4$ , it is possible to obtain a $Y_{5}$ tree. We then place the $8$ copies of $Y_{5}$ trees follows from $(3_{a_{i j}} 2_{j} 1_{i} 2_{j + 3}; 1_{i} 3_{k - 1})$ in $S_{2}$ . All together leads a $Y_{5}$ tree decomposition for $K_{8, 8, 6}$ . As a consequence of it, a gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{8, 8, 6})$ may derived through use of Lemma 2.3.

(3) A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{8, 8, 6})$ can be derived as follows:
Let $V (K_{8, 8, 7})$ $=$ ${(⋃_{p = 1}^{2} p_{q}, 1 \leq q \leq 8) \cup (3_{q}, 1 \leq q \leq 7)}$ . By removing the backword diagonal entries from Table 2, we can attain a latin square $L$ in Table 5. By using Table 5, we can produce a set $S_{3}$ of $Y_{5}$ tree decomposition for $K_{8, 8, 7}$ as per the following:

Table 5 Dropped the backword diagonal entries from $L_{8}$
1	2	3	4	5	6	7	$\times$
2	3	4	5	6	7	$\times$	1
3	4	5	6	7	$\times$	1	2
4	5	6	7	$\times$	1	2	3
5	6	7	$\times$	1	2	3	4
6	7	$\times$	1	2	3	4	5
7	$\times$	1	2	3	4	5	6
$\times$	1	2	3	4	5	6	7

$∙$ Consider the set of $Y$ tree cells ${(a_{i j}, a_{i (j + 4)}, a_{(i + 4) j}, a_{(i + 4) (j + 4)})}, (i, j) \in {(1, 1), (1, 2), (1, 3),$ $(2, 1), (2, 2) (2, 4), (3, 1), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)}$ . It is possible to obtain a $Y$ tree cell corresponding to each $(i, j)$ . All together gives $12$ copies of $Y$ tree cells. These $Y$ tree cells provides the following $36$ copies of $Y_{5}$ trees.

When $i = j$

$1_{i + h} 2_{j + k} 1_{i} 3_{a_{(i + h) (j + k)}}; 1_{i} 3_{4}$ , $2_{j + k} 3_{a_{(i + h) (j + k)}} 1_{i + h} 3_{4}; 1_{i + h} 3_{a_{i (j + k)}}$ , $3_{a_{i j}} 2_{j} 3_{a_{(i + h) j}} 2_{j + k}; 3_{a_{(i + h) j}} 1_{i}$ .
When $i \neq j$

$1_{i + h} 2_{j + k} 1_{i} 3_{a_{(i + h) (j + k)}}; 1_{i} 2_{j}$ , $2_{j + k} 3_{a_{(i + h) (j + k)}} 1_{i + h} 2_{j}; 1_{i + h} 3_{a_{i (j + k)}}$ , $3_{a_{i j}} 2_{j} 3_{a_{(i + h) j}} 2_{j + k}; 3_{a_{(i + h) j}} 1_{i}$ .

$∙$ For all $(i, j) \in {(1, 4), (2, 3), (3, 2), (4, 1)}$ , $a_{i j} = 4$ , it is possible to obtain a $Y_{5}$ tree. We then place the $4$ copies of $Y_{5}$ trees follows from $(3_{a_{i j}} 2_{j} 1_{i} 2_{9 - i}; 1_{i} 2_{i})$ in $S_{3}$ .

$∙$ For all $(i, j) \in {(5, 8), (6, 7), (7, 6), (8, 5)}$ , $a_{i j} = 4$ , it is possible to obtain a $Y_{5}$ tree. We then place the $4$ copies of $Y_{5}$ trees follows from $(3_{a_{i j}} 2_{j} 1_{i} 2_{9 - i}; 1_{i} 2_{i - 4})$ in $S_{3}$ . All together leads a $Y_{5}$ tree decomposition for $K_{8, 8, 7}$ . As a consequence of it, a gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{8, 8, 7})$ may derived through use of Lemma 2.3.

From Cases 1, 2 and 3, we can concluded that, a gregarious $Y_{5}$ tree decomposition exists for $E_{2} (G)$ , $G$ $\in$ $G = {K_{8, 8, 5}, K_{8, 8, 6}, K_{8, 8, 7}}$ .

Lemma 2.7. A gregarious

Y_{5}

tree decomposition for each

G

\in

G

=

{K_{8, 8, 10}

K_{8, 8, 11}

K_{8, 8, 12}}

is admissible in

E_{2} (G)

Proof. (1) A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{8, 8, 10})$ can be derived as follows:

Let $V (K_{8, 8, 10})$ $=$ ${(⋃_{p = 1}^{2} p_{q}, 1 \leq q \leq 8) \cup (3_{1}, 3_{2}, 3_{3}, 3_{4}, 3_{5}, 3_{6}, 3_{7}, 3_{8}, \infty_{1}, \infty_{2})}$ . By using the latin square in Table 2, we can produce a set $S_{1}$ of $Y_{5}$ tree decomposition for $K_{8, 8, 10}$ as follows:

$∙$ As discussed in Remark 2.1, if $a_{i j} = a_{(i + h) (j + k)} = 5$ and $a_{i (j + k)} = a_{(i + h) j} = 1$ , we get the following $Y$ tree cells ${(a_{15}, a_{11}, a_{55}, a_{51}), (a_{24}, a_{28}, a_{64}, a_{68}), (a_{33}, a_{37}, a_{73}, a_{77}), (a_{42}, a_{46}, a_{82}, a_{86})}$ . It follows that the $Y$ tree cells yield $12$ copies of $Y_{5}$ trees.

$∙$ For all $(i, j) \in {(1, 2), (2, 1), (3, 8), (4, 7), (5, 6), (6, 5), (7, 4), (8, 3)}$ , we have $a_{i j} = 2$ and for all $(i, j) \in {(1, 3), (2, 2), (3, 1), (4, 8), (5, 7), (6, 6), (7, 5), (8, 4)}$ , we have $a_{i j} = 3$ . It is possible to obtain a $Y_{5}$ tree corresponding to each $(i, j)$ , such as $(3_{a_{i j}} 2_{j} 1_{i} \infty_{k}; 1_{i} 3_{a_{i j} + 1})$ , if $a_{i j} = k + 1$ , $k = 1, 2$ . Thus we may include these $16$ copies of $Y_{5}$ trees in $S_{1}$ .

$∙$ For all $(i, j) \in {(1, 4), (2, 3), (3, 2), (4, 1), (5, 8), (6, 7), (7, 6), (8, 5)}$ , we have $a_{i j} = 4$ . It is possible to obtain a $Y_{5}$ tree corresponding to each $(i, j)$ , such as $(3_{a_{i j}} 2_{j} 1_{i} 3_{k + 5}; 1_{i} 3_{k - 1})$ , if $a_{i j} = k + 1$ , $k = 3$ . Thus we may include these $8$ copies of $Y_{5}$ trees in $S_{1}$ .

$∙$ For all $(i, j) \in {(1, 6), (2, 5), (3, 4), (4, 3)}$ , we have $a_{i j} = 6$ . It is possible to obtain a $Y_{5}$ tree corresponding to each $(i, j)$ , such as $(3_{a_{i j}} 1_{i} 2_{j} \infty_{k - 3}; 2_{j} 3_{a_{i j} + 1})$ , if $a_{i j} = k + 2$ , $k = 4$ . Thus we may include these $4$ copies of $Y_{5}$ trees in $S_{1}$ .

$∙$ For all $(i, j) \in {(5, 2), (6, 1), (7, 8), (8, 7)}$ , we have $a_{i j} = 6$ . It is possible to obtain a $Y_{5}$ tree corresponding to each $(i, j)$ , such as $(2_{j + 2} 1_{i} 2_{j} \infty_{1}; 2_{j} 3_{a_{i j} + 1})$ , if $a_{i j} = k + 2$ , $k = 4$ . Thus we may include these $4$ copies of $Y_{5}$ trees in $S_{1}$ .

$∙$ For all $(i, j) \in {(1, 7), (2, 6), (3, 5), (4, 4), (5, 3), (6, 2), (7, 1), (8, 8)}$ , we have $a_{i j} = 7$ . It is possible to obtain a $Y_{5}$ tree corresponding to each $(i, j)$ , such as $(3_{a_{i j}} 1_{i} 2_{j} \infty_{k - 3}; 2_{j} 3_{k + 3})$ , if $a_{i j} = k + 2$ , $k = 5$ . Thus we may include these $8$ copies of $Y_{5}$ trees in $S_{1}$ .

$∙$ For all $(i, j) \in {(1, 8), (2, 7), (3, 6), (4, 5)}$ , we have $a_{i j} = 8$ . It is possible to obtain a $Y_{5}$ tree corresponding to each $(i, j)$ , such as $(1_{i} 2_{j} 3_{(a_{i j} - 2)} 2_{i}; 3_{(a_{i j} - 2)} 1_{i + 4})$ , if $a_{i j} = k + 2$ , $k = 6$ . Thus we may include these $4$ copies of $Y_{5}$ trees in $S_{1}$ .

All together leads a $Y_{5}$ tree decomposition for $K_{8, 8, 10}$ . As a consequence of it, a gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{8, 8, 10})$ may derived through the use of Lemma 2.3.

(2) A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{8, 8, 11})$ can be derived as follows:

Let $V (K_{8, 8, 11})$ $=$ ${(⋃_{p = 1}^{2} p_{q}, 1 \leq q \leq 8) \cup (3_{1}, 3_{2}, 3_{3}, 3_{4}, 3_{5}, 3_{6}, 3_{7}, 3_{8}, \infty_{1}, \infty_{2}, \infty_{3})}$ . By using the latin square in Table 2, we can produce a set $S_{2}$ of $Y_{5}$ tree decomposition for $K_{8, 8, 11}$ as follows:

$∙$ As discussed in Remark 2.1, if $a_{i j} = a_{(i + h) (j + k)} = 5$ and $a_{i (j + k)} = a_{(i + h) j} = 1$ , we get the following $Y$ tree cells ${(a_{15}, a_{11}, a_{55}, a_{51}), (a_{24}, a_{28}, a_{64}, a_{68}), (a_{33}, a_{37}, a_{73}, a_{77}), (a_{42}, a_{46}, a_{82}, a_{86})}$ . It follows that the $Y$ tree cells yield $12$ copies of $Y_{5}$ trees.

$∙$ For all $(i, j) \in {(1, 2), (2, 1), (3, 8), (4, 7), (5, 6), (6, 5), (7, 4), (8, 3)$ , we have $a_{i j} = 2$ and for all $(i, j) \in {(1, 3), (2, 2), (3, 1), (4, 8), (5, 7), (6, 6), (7, 5), (8, 4)}$ , we have $a_{i j} = 3$ . It is possible to obtain a $Y_{5}$ tree corresponding to each $(i, j)$ , such as $(3_{a_{i j}} 2_{j} 1_{i} \infty_{k}; 1_{i} 3_{k + 2})$ , if $a_{i j} = k + 1$ , $k = 1, 2$ . Thus we may include these $16$ copies of $Y_{5}$ trees in $S_{2}$ .

$∙$ For all $(i, j) \in {(1, 4), (2, 3), (3, 2), (4, 1), (5, 8), (6, 7), (7, 6), (8, 5)}$ , we have $a_{i j} = 4$ . It is possible to obtain a $Y_{5}$ tree corresponding to each $(i, j)$ , such as $(3_{a_{i j}} 2_{j} 1_{i} \infty_{k}; 1_{i} 3_{k - 1})$ , if $a_{i j} = k + 1$ , $k = 3$ . Thus we may include these $8$ copies of $Y_{5}$ trees in $S_{2}$ .

$∙$ For all $(i, j) \in {(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1), (7, 8), (8, 7)}$ , we have $a_{i j} = 6$ and for all $(i, j) \in {(1, 7), (2, 6), (3, 5), (4, 4), (5, 3), (6, 2), (7, 1), (8, 8)}$ , we have $a_{i j} = 7$ . It is possible to obtain a $Y_{5}$ tree corresponding to each $(i, j)$ , such as $(3_{a_{i j}} 1_{i} 2_{j} \infty_{k}; 2_{j} 3_{(a_{i j} + 1)})$ , if $a_{i j} = k + 5$ , $k = 1, 2$ . Thus we may include these $16$ copies of $Y_{5}$ trees in $S_{2}$ .

$∙$ For all $(i, j) \in {(1, 8), (2, 7), (3, 6), (4, 5), (5, 4), (6, 3), (7, 2), (8, 1)}$ , we have $a_{i j} = 8$ . It is possible to obtain a $Y_{5}$ tree corresponding to each $(i, j)$ , such as $(3_{a_{i j}} 1_{i} 2_{j} \infty_{k}; 2_{j} 3_{(a_{i j} - 2)})$ , if $a_{i j} = k + 5$ , $k = 3$ . Thus we may include these $8$ copies of $Y_{5}$ trees in $S_{2}$ .

All together leads a $Y_{5}$ tree decomposition for $K_{8, 8, 11}$ . As a consequence of it, a gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{8, 8, 11})$ may derived through use of Lemma 2.3.

(3) A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{8, 8, 12})$ can be derived as follows:

Let $V (K_{8, 8, 12})$ $=$ ${(⋃_{p = 1}^{2} p_{q}, 1 \leq q \leq 8) \cup (3_{1}, 3_{2}, 3_{3}, 3_{4}, 3_{5}, 3_{6}, 3_{7}, 3_{8}, \infty_{1}, \infty_{2}, \infty_{3}, \infty_{4})}$ . By using the latin square $L$ in Table 2, we can produce a set $S_{3}$ for $Y_{5}$ tree decomposition of $K_{8, 8, 12}$ as follows:

$∙$ For all $(i, j) \in {(1, 1), (2, 8), (3, 7), (4, 6), (5, 5), (6, 4), (7, 3), (8, 2)}$ , we have $a_{i j} = 1$ , for all $(i, j) \in {(1, 2), (2, 1), (3, 8), (4, 7), (5, 6), (6, 5), (7, 4), (8, 3)}$ , we have $a_{i j} = 2$ and for all $(i, j) \in {(1, 3), (2, 2), (3, 1), (4, 8), (5, 7), (6, 6), (7, 5), (8, 4)}$ , we have $a_{i j} = 3$ . It is possible to obtain a $Y_{5}$ tree corresponding to each $(i, j)$ , such as $(3_{a_{i j}} 2_{j} 1_{i} \infty_{k}; 1_{i} 3_{k + 1})$ , if $a_{i j} = k$ , $k = 1, 2, 3$ . Thus we may include these $24$ copies of $Y_{5}$ trees in $S_{3}$ .

$∙$ For all $(i, j) \in {(1, 4), (2, 3), (3, 2), (4, 1), (5, 8), (6, 7), (7, 6), (8, 5)}$ , we have $a_{i j} = 4$ . It is possible to obtain a $Y_{5}$ tree corresponding to each $(i, j)$ , such as $(3_{a_{i j}} 2_{j} 1_{i} \infty_{k}; 1_{i} 3_{k - 3})$ , if $a_{i j} = k$ , $k = 4$ . Thus we may include these $8$ copies of $Y_{5}$ trees in $S_{3}$ .

$∙$ For all $(i, j) \in {(1, 5), (2, 4), (3, 3), (4, 2), (5, 1), (6, 8), (7, 7), (8, 6)}$ , we have $a_{i j} = 5$ , for all $(i, j) \in {(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1), (7, 8), (8, 7)}$ , we have $a_{i j} = 6$ and for all $(i, j) \in {(1, 7), (2, 6), (3, 5), (4, 4), (5, 3), (6, 2), (7, 1), (8, 8)}$ , we have $a_{i j} = 7$ . It is possible to obtain a $Y_{5}$ tree corresponding to each $(i, j)$ , such as $(3_{a_{i j}} 1_{i} 2_{j} \infty_{k}; 2_{j} 3_{(a_{i j} + 1)})$ , if $a_{i j} = k + 4$ , $k = 1, 2, 3$ . Thus we may include these $24$ copies of $Y_{5}$ trees in $S_{3}$ .

$∙$ For all $(i, j) \in {(1, 8), (2, 7), (3, 6), (4, 5), (5, 4), (6, 3), (7, 2), (8, 1),}$ , we have $a_{i j} = 8$ . It is possible to obtain a $Y_{5}$ tree corresponding to each $(i, j)$ , such as $(3_{a_{i j}} 1_{i} 2_{j} \infty_{k}; 2_{j} 3_{(k + 1)})$ , if $a_{i j} = k + 4$ , $k = 4$ . Thus we may include these $8$ copies of $Y_{5}$ trees in $S_{3}$ .

All together leads a $Y_{5}$ tree decomposition for $K_{8, 8, 12}$ . As a consequence of it, a gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{8, 8, 12})$ may derived through use of Lemma 2.3.

From Cases 1, 2 and 3, we can cocluded that, a gregarious $Y_{5}$ tree decomposition exists for $E_{2} (G)$ , $G$ $\in$ $G = {K_{8, 8, 10}, K_{8, 8, 11}, K_{8, 8, 12}}$ .

Lemma 2.8. A gregarious

Y_{5}

tree decomposition for each graph

G

\in

G

=

{K_{12, 12, 7}

K_{12, 12, 10}}

is admissible in

E_{2} (G)

Proof. (1) A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{12, 12, 7})$ can be derived as follows:
Let $V (K_{12, 12, 7})$ $=$ ${(⋃_{p = 1}^{2} p_{q}, 1 \leq q \leq 12) \cup (3_{q}, 1 \leq q \leq 7)}$ . By removing the entries 8, 9, 10, 11 and 12 from Table 6, we can attain a latin square $L$ in Table 7. By using Table 7, we can produce a set $S_{1}$ of $Y_{5}$ tree decomposition for $K_{12, 12, 7}$ as follows:

Table 6 Latin square of order $12$ ( $L_{12}$ )
1	2	3	4	5	6	7	8	9	10	11	12
2	3	4	5	6	7	8	9	10	11	12	1
3	4	5	6	7	8	9	10	11	12	1	2
4	5	6	7	8	9	10	11	12	1	2	3
5	6	7	8	9	10	11	12	1	2	3	4
6	7	8	9	10	11	12	1	2	3	4	5
7	8	9	10	11	12	1	2	3	4	5	6
8	9	10	11	12	1	2	3	4	5	6	7
9	10	11	12	1	2	3	4	5	6	7	8
10	11	12	1	2	3	4	5	6	7	8	9
11	12	1	2	3	4	5	6	7	8	9	10
12	1	2	3	4	5	6	7	8	9	10	11

Table 7 Dropped the entries $8, 9, 10, 11, 12$ from $L_{12}$
1	2	3	4	5	6	7	$\times$	$\times$	$\times$	$\times$	$\times$
2	3	4	5	6	7	$\times$	$\times$	$\times$	$\times$	$\times$	1
3	4	5	6	7	$\times$	$\times$	$\times$	$\times$	$\times$	1	2
4	5	6	7	$\times$	$\times$	$\times$	$\times$	$\times$	1	2	3
5	6	7	$\times$	$\times$	$\times$	$\times$	$\times$	1	2	3	4
6	7	$\times$	$\times$	$\times$	$\times$	$\times$	1	2	3	4	5
7	$\times$	$\times$	$\times$	$\times$	$\times$	1	2	3	4	5	6
$\times$	$\times$	$\times$	$\times$	$\times$	1	2	3	4	5	6	7
$\times$	$\times$	$\times$	$\times$	1	2	3	4	5	6	7	$\times$
$\times$	$\times$	$\times$	1	2	3	4	5	6	7	$\times$	$\times$
$\times$	$\times$	1	2	3	4	5	6	7	$\times$	$\times$	$\times$
$\times$	1	2	3	4	5	6	7	$\times$	$\times$	$\times$	$\times$

$∙$ Consider the set of $Y$ tree cells ${a_{i j}, a_{i (j + 6)}, a_{(i + 6) j}, a_{(i + 6) (j + 6)}}$ , where $(i, j) \in {(1, 1), (2, 6),$ $(3, 5), (4, 4), (5, 3), (6, 2)}$ . It is possible to obtain a $Y$ tree cell corresponding to each $(i, j)$ . All together gives $6$ copies of $Y$ tree cells. As discussed in Remark 2.1, these $Y$ tree cells will provide $18$ copies of $Y_{5}$ trees.

$∙$ For all $(i, j) \in {(1, 2), (2, 1), (3, 12), (4, 11), (5, 10), (6, 9), (7, 8), (8, 7), (9, 6), (10, 5), (11, 4), (12, 3)}$ , we have $a_{i j} = 2$ . For all $(i, j) \in {(1, 3), (2, 2), (3, 1), (4, 12), (5, 11), (6, 10), (7, 9), (8, 8), (9, 7), (10, 6), (11, 5), (12, 4)}$ , we have $a_{i j} = 3$ . For all $(i, j) \in {(1, 4), (2, 3), (3, 2), (4, 1), (5, 12), (6, 11), (7, 10), (8, 9), (9, 8), (10, 7), (11, 6), (12, 5)}$ , we have $a_{i j} = 4$ . And for all $(i, j) \in {(1, 5), (2, 4), (3, 3), (4, 2), (5, 1), (6, 12), (7, 11), (8, 10), (9, 9), (10, 8), (11, 7), (12, 6)}$ , we have $a_{i j} = 5$ . It is possible to obtain a $Y_{5}$ tree corresponding to each $(i, j)$ , such as $(3_{a_{i j}} 2_{j} 1_{i} 2_{k + 7 - i}; 1_{i} 3_{k + 1})$ , if $a_{i j} = k$ , $k = 2, 3, 4, 5$ . Thus we may include these $48$ copies of $Y_{5}$ trees in $S_{1}$ .

$∙$ For all $(i, j) \in {(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1), (7, 12), (8, 11), (9, 10), (10, 9), (11, 8), (12, 7)}$ , we have $a_{i j} = 6$ . It is possible to obtain a $Y_{5}$ tree corresponding to each $(i, j)$ , such as $(3_{a_{i j}} 2_{j} 1_{i} 2_{k + 7 - i}; 1_{i} 3_{k - 4})$ , if $a_{i j} = k$ , $k = 6$ . Thus we may include these $12$ copies of $Y_{5}$ trees in $S_{1}$ . All together leads a $Y_{5}$ tree decomposition for $K_{12, 12, 7}$ . As a consequence of it, a gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{12, 12, 7})$ may derived through use of Lemma 2.3.

(2) A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{12, 12, 10})$ can be derived as follows:

Let $V (K_{12, 12, 10})$ $=$ ${(⋃_{p = 1}^{2} p_{q}, 1 \leq q \leq 12) \cup (3_{q}, 1 \leq q \leq 10)}$ . By removing the entries 11 and 12 from Table 6, we can attain a latin square $L$ in Table 8. By using Table 8, we can produce a set $S_{2}$ of $Y_{5}$ tree decomposition for $K_{12, 12, 10}$ as follows:

Table 8 Dropped the entries $11, 12$ from $L_{12}$
1	2	3	4	5	6	7	8	9	10	$\times$	$\times$
2	3	4	5	6	7	8	9	10	$\times$	$\times$	1
3	4	5	6	7	8	9	10	$\times$	$\times$	1	2
4	5	6	7	8	9	10	$\times$	$\times$	1	2	3
5	6	7	8	9	10	$\times$	$\times$	1	2	3	4
6	7	8	9	10	$\times$	$\times$	1	2	3	4	5
7	8	9	10	$\times$	$\times$	1	2	3	4	5	6
8	9	10	$\times$	$\times$	1	2	3	4	5	6	7
9	10	$\times$	$\times$	1	2	3	4	5	6	7	8
10	$\times$	$\times$	1	2	3	4	5	6	7	8	9
$\times$	$\times$	1	2	3	4	5	6	7	8	9	10
$\times$	1	2	3	4	5	6	7	8	9	10	$\times$

$∙$ Consider the set of $Y$ tree cells ${a_{i j}, a_{i (j + 6)}, a_{(i + 6) j}, a_{(i + 6) (j + 6)}}$ , where $(i, j) \in {(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 6), (3, 1), (3, 2), (3, 5), (3, 6), (4, 1), (4, 4), (4, 5), (4, 6), (5, 3), (5, 4), (5, 5), (5, 6), (6, 2), (6, 3) (6, 4), (6, 5)}$ . It is possible to obtain a $Y$ tree cell for each $(i, j)$ . All together gives $24$ copies of $Y$ tree cells. As discussed in Remark 2.1, the $Y$ tree cells will provide $72$ copies of $Y_{5}$ trees.

$∙$ For all $(i, j) \in {(1, 5), (2, 4), (3, 3), (4, 2), (5, 1), (6, 12), (7, 11), (8, 10), (9, 9), (10, 8), (11, 7), (12, 6)}$ , we have $a_{i j} = 5$ . It is possible to obtain a $Y_{5}$ tree corresponding to each $(i, j)$ , such as $(3_{a_{i j}} 2_{j} 1_{i} 2_{k + 7 - i}; 1_{i} 3_{k + 1})$ , if $a_{i j} = k$ , $k = 5$ . Thus we may include these $12$ copies of $Y_{5}$ trees in $S_{2}$ .

$∙$ For all $(i, j) \in {(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1), (7, 12), (8, 11), (9, 10), (10, 9), (11, 8), (12, 7)}$ , we have $a_{i j} = 6$ . It is possible to obtain a $Y_{5}$ tree for each $(i, j)$ , such as $(3_{a_{i j}} 2_{j} 1_{i} 2_{k + 7 - i}; 1_{i} 3_{k - 1})$ , if $a_{i j} = k$ , $k = 6$ . Thus we may include these $12$ copies of $Y_{5}$ trees in $S_{2}$ .

All together leads a $Y_{5}$ tree decomposition for $K_{12, 12, 10}$ . As a consequence of it, a gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{12, 12, 10})$ may derived through use of Lemma 2.3.

From Cases 1 and 2, we can concluded that, a gregarious $Y_{5}$ tree decomposition exists for $E_{2} (G)$ , $G$ $\in$ $G = {K_{12, 12, 7}, K_{12, 12, 10}}$ .

Lemma 2.9. A gregarious

Y_{5}

tree decomposition for each graph

G

\in

G

=

{K_{10} ∖ K_{7}, K_{11} ∖ K_{6}, K_{12} ∖ K_{5}, K_{13} ∖ K_{5}, K_{14} ∖ K_{6}, K_{15} ∖ K_{7}, K_{16} ∖ K_{8}, K_{19} ∖ K_{14}, K_{20} ∖ K_{13}, K_{29} ∖ K_{20}, K_{35} ∖ K_{30}}

is admissible in

E_{2} (G)

Proof. (1) Let us consider $V (K_{10} ∖ K_{7}) = {1, 2, 3, \dots, 10}$ and $S_{1} = {(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)} .$ It follows that, the set $S_{1}$ provides a $Y_{5}$ tree decomposition of $K_{10} ∖ K_{7}$ .

(2) By taking $V (K_{11} ∖ K_{6}) = {1, 2, 3, \dots, 11}$ , the set $S_{2}$ given bellow derives a $Y_{5}$ tree decomposition of $K_{11} ∖ K_{6}$ . $\begin{aligned} S_{2} = & {(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)} . \end{aligned}$

(3) By taking $V (K_{12} ∖ K_{5}) = {1, 2, 3, \dots, 12}$ , a $Y_{5}$ tree decomposition for $K_{12} ∖ K_{5}$ is contained with in the set $S_{3}$ mentioned bellow. $\begin{aligned} S_{3} = & {(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)} . \end{aligned}$

(4) Let $V (K_{13} ∖ K_{5}) = {1, 2, 3, \dots, 13}$ , the collection $S_{4}$ gives a $Y_{5}$ tree decomposition of $K_{13} ∖ K_{5}$ . $\begin{aligned} S_{4} = & {(1 3 4 10; 4 13), (6 4 5 11; 5 1), (3 5 6 12; 6 8), (4 2 7 13; 7 3), (5 7 8 1; 8 3), \\ (6 13 2 3; 2 5), (7 6 1 13; 1 10), (9 3 6 10; 6 11), (9 4 7 11; 7 12), (10 5 8 12; 8 4), \\ (11 4 12 5; 12 3), (12 1 11 8; 11 2), (13 8 9 6; 9 1), (1 7 9 2; 9 5), (5 13 3 10; 3 11), \\ (12 2 10 7; 10 8), (4 1 2 6; 2 8)} . \end{aligned}$

(5) By considering $V (K_{14} ∖ K_{6}) = {1, 2, 3, \dots, 14}$ , the set $S_{5}$ must be a $Y_{5}$ tree decomposition of $K_{14} ∖ K_{6}$ . $\begin{aligned} S_{5} = & {(14 3 4 10; 4 1), (14 4 5 11; 5 1), (3 5 6 12; 6 14), (4 2 7 14; 7 3), (13 7 8 1; 8 3), \\ (6 13 2 3; 2 5), (7 6 1 13; 1 10), (9 3 6 10; 6 11), (9 4 7 11; 7 12), (10 5 8 12; 8 4), \\ (11 4 12 5; 12 3), (12 1 11 8; 11 2), (13 8 9 6; 9 1), (1 7 9 2; 9 5), (5 13 3 10; 3 11), \\ (12 2 10 7; 10 8), (3 1 2 8; 2 14), (13 4 6 8; 6 2), (7 5 14 8; 14 1)} . \end{aligned}$

(6) Let $V (K_{15} ∖ K_{7}) = {1, 2, 3, \dots, 15}$ . The set $S_{6}$ leads a $Y_{5}$ tree decomposition of $K_{15} ∖ K_{7}$ . $\begin{aligned} S_{6} = & {(15 3 4 10; 4 1), (15 4 5 11; 5 10), (3 5 6 12; 6 14), (15 2 7 14; 7 3), \\ (13 7 8 15; 8 2), (6 13 2 5; 2 14), (7 6 1 13; 1 10), (9 3 6 10; 6 15), (9 4 7 11; 7 12), \\ (15 5 8 12; 8 4), (11 4 12 5; 12 3), (12 1 11 8; 11 6), (13 8 9 6; 9 1), (1 7 9 2; 9 5), \\ (5 13 3 10; 3 11), (12 2 10 7; 10 8), (2 1 3 8; 3 14), (13 4 6 8; 6 2), (7 5 14 8; 14 1), \\ (7 15 1 8; 1 5), (14 4 2 3; 2 11)} . \end{aligned}$

(7) By considering $V (K_{16} ∖ K_{8}) = {1, 2, 3, \dots, 16}$ , the set $S_{7}$ provides a $Y_{5}$ tree decomposition of $K_{16} ∖ K_{8}$ . $\begin{aligned} S_{7} = & {(3 6 15 1; 15 7), (15 5 4 8; 4 9), (13 7 5 1; 5 14), (13 3 2 16; 2 6), \\ (8 13 4 16; 4 12), (14 1 6 16; 6 5), (14 2 5 16; 5 13), (14 4 3 16; 3 15), (14 6 8 16; 8 12), \\ (11 7 1 16; 1 13), (15 2 7 16; 7 14), (9 3 8 1; 8 14), (4 7 9 1; 9 8), (10 6 9 2; 9 5), \\ (15 8 2 1; 2 13), (5 8 10 1; 10 4), (6 7 10 3; 10 5), (11 5 3 1; 3 14), (4 2 12 5; 12 7), \\ (10 2 11 1; 11 3), (7 8 11 4; 11 6), (13 6 4 1; 4 15), (7 3 12 1; 12 6)} . \end{aligned}$

(8) Let $V (K_{19} ∖ K_{14}) = {1, 2, 3, \dots, 19}$ . A $Y_{5}$ tree decomposition of $K_{19} ∖ K_{14}$ belongs to $S_{8}$ . $\begin{aligned} S_{8} = & {(3 18 5 4; 5 2), (2 19 1 4; 1 6), (3 1 2 6; 2 14), (4 2 3 7; 3 16), (5 6 4 3; 4 16), \\ (6 3 19 5; 19 4), (7 1 12 3; 12 5), (1 10 2 18; 2 13), (16 2 9 4; 9 1), (5 15 2 8; 2 7), \\ (5 11 4 10; 4 17), (17 2 11 3; 11 1), (4 7 5 8; 5 1), (10 5 13 3; 13 1), (1 16 5 9; 5 14), \\ (2 12 4 13; 4 14), (5 3 15 4; 15 1), (4 18 1 8; 1 14), (10 3 17 1; 17 5), (4 8 3 9; 3 14)} . \end{aligned}$

(9) Let $V (K_{20} ∖ K_{13}) = {1, 2, 3, \dots, 20}$ . A $Y_{5}$ tree decomposition of $K_{20} ∖ K_{13}$ is contained in $S_{9}$ . $\begin{aligned} S_{9} = & {(3 6 15 1; 15 7), (20 5 4 19; 4 9), (13 7 5 1; 5 14), (13 3 2 20; 2 6), \\ (6 13 4 18; 4 12), (20 1 6 12; 6 5), (8 2 5 16; 5 13), (20 4 15 3; 15 5), (19 6 7 16; 7 12), \\ (11 7 1 16; 1 13), (15 2 7 19; 7 20), (20 3 19 1; 19 5), (18 7 9 1; 9 2), (10 6 9 3; 9 5), \\ (16 3 18 5; 18 6), (6 17 2 13; 2 18), (4 10 1 12; 1 18), (4 7 10 3; 10 5), (11 5 3 1; 3 14), \\ (4 2 12 5; 12 3), (10 2 11 1; 11 3), (20 6 4 1; 4 3), (7 3 8 1; 8 6), (8 7 14 6; 14 1), \\ (8 4 16 2; 16 6), (8 5 17 7; 17 3), (6 11 4 14; 4 17), (17 1 2 14; 2 19)} . \end{aligned}$

(10) Let $V (K_{29} ∖ K_{20}) = {1, 2, 3, \dots, 29}$ . A $Y_{5}$ tree decomposition of $K_{29} ∖ K_{20}$ has been constructed as follows: $\begin{aligned} S_{10} = & {(1 9 5 12; 5 17), (2 10 6 13; 6 18), (7 11 3 14; 3 19), (4 12 8 15; 8 20), \\ (5 13 9 16; 9 21), (6 14 1 20; 1 22), (5 27 2 21; 2 23), (6 27 3 22; 3 24), \\ (7 3 4 23; 4 25), (8 29 5 24; 5 26), (10 1 6 25; 6 28), (11 2 24 4; 24 9), \\ (12 7 14 5; 14 4), (13 4 15 3; 15 2), (10 5 16 6; 16 3), (11 6 7 8; 7 26), \\ (12 3 10 9; 10 8), (13 8 11 9; 11 4), (8 27 7 18; 7 29), (9 28 8 19; 8 18), \\ (29 1 12 9; 12 2), (6 2 13 3; 13 1), (22 7 4 29; 4 26), (7 28 3 23; 3 25), \\ (17 9 7 23; 7 20), (25 1 8 24; 8 21), (26 2 9 25; 9 22), (15 5 1 26; 1 23), \\ (26 6 5 25; 5 4), (3 8 9 14; 9 29), (14 2 7 10; 7 17), (8 4 9 20; 9 19), \\ (22 2 1 11; 1 21), (3 6 15 1; 15 7), (28 4 16 2; 16 8), (5 8 17 3; 17 6), \\ (6 9 18 4; 18 1), (7 1 19 5; 19 2), (8 2 20 6; 20 3), (9 3 21 7; 21 4), \\ (10 4 22 8; 22 5), (11 5 23 9; 23 6), (12 6 24 1; 24 7), (13 7 25 2; 25 8), \\ (14 8 26 3; 26 9), (15 9 27 4; 27 1), (16 1 28 5; 28 2), (17 2 29 6; 29 3), \\ (18 3 1 17; 1 4), (19 4 2 18; 2 5), (20 5 7 19; 7 16), (21 6 4 20; 4 17), \\ (2 3 5 21; 5 18), (23 8 6 22; 6 19)} . \end{aligned}$

(11) Let $V (K_{35} ∖ K_{30}) = {1, 2, 3, \dots, 35}$ . A $Y_{5}$ tree decomposition of $K_{35} ∖ K_{30}$ is shown bellow: $\begin{aligned} S_{11} = & {(3 18 5 1; 5 2), (4 19 1 2; 1 3), (5 20 2 3; 2 4), (1 21 3 4; 3 24), \\ (2 22 4 13; 4 6), (3 23 5 14; 5 7), (4 24 1 15; 1 8), (4 25 2 16; 2 9), \\ (1 26 3 19; 3 10), (2 27 4 18; 4 11), (3 28 5 25; 5 12), (4 29 1 20; 1 13), \\ (5 30 2 13; 2 14), (1 31 3 14; 3 15), (2 32 4 15; 4 16), (3 33 5 16; 5 17), \\ (4 34 1 17; 1 18), (5 35 2 18; 2 19), (3 17 2 23; 2 7), (5 26 4 21; 4 23), \\ (1 27 5 22; 5 24), (2 28 1 23; 1 25), (3 29 2 24; 2 26), (4 30 3 25; 3 27), \\ (5 31 4 28; 4 20), (1 32 5 29; 5 19), (2 33 1 30; 1 14), (3 34 2 31; 2 15), \\ (4 35 3 32; 3 16), (6 1 4 33; 4 17), (20 3 5 34; 5 4), (8 3 6 2; 6 5), (9 4 7 3; 7 1), \\ (10 5 8 4; 8 2), (11 1 9 5; 9 3), (12 2 10 1; 10 4), (13 3 11 2; 11 5), \\ (14 4 12 3; 12 1), (3 22 1 16; 1 35), (2 21 5 13; 5 15)} . \end{aligned}$

From (1) – (11), we have got a $Y_{5}$ tree decomposition for each $G$ $\in$ $G$ $=$ ${K_{10} ∖ K_{7}, K_{11} ∖ K_{6}, K_{12} ∖ K_{5}, K_{13} ∖ K_{5}, K_{14} ∖ K_{6}, K_{15} ∖ K_{7}, K_{16} ∖ K_{8}, K_{19} ∖ K_{14}, K_{20} ∖ K_{13}, K_{29} ∖ K_{20}, K_{35} ∖ K_{30}}$ . By applying Lemma 2.3, we can produce a gregarious $Y_{5}$ tree decomposition for $E_{2} (G)$ , $G$ $\in$ $G$ $=$ ${K_{10} ∖ K_{7}, K_{11} ∖ K_{6}, K_{12} ∖ K_{5}, K_{13} ∖ K_{5}, K_{14} ∖ K_{6}, K_{15} ∖ K_{7}, K_{16} ∖ K_{8}, K_{19} ∖ K_{14}, K_{20} ∖ K_{13}, K_{29} ∖ K_{20}, K_{35} ∖ K_{30}}$ .

Lemma 2.10. A gregarious

Y_{5}

tree decomposition for each graph

G

\in

G

=

{K_{i}}

is admissible in

E_{2} (K_{i})

, for all

i \in {5, 6, 7}

Proof. A gregarious $Y_{5}$ tree decomposition of $E_{2} (K_{i})$ , $i \in {5, 6, 7}$ have been discribed as follows: $\begin{aligned} E_{2} (K_{5}) = & {(1_{2} 2_{2} 3_{1} 4_{2}; 3_{1} 5_{2}) \oplus (1_{1} 2_{1} 3_{2} 4_{1}; 3_{2} 5_{1}) \oplus (2_{1} 4_{2} 1_{1} 3_{2}; 1_{1} 5_{2}) \oplus \\ (2_{2} 4_{1} 1_{2} 3_{1}; 1_{2} 5_{1}) \oplus (1_{1} 3_{1} 2_{1} 4_{1}; 2_{1} 5_{1}) \oplus (1_{2} 3_{2} 2_{2} 4_{2}; 2_{2} 5_{2}) \oplus \\ (2_{1} 1_{2} 5_{2} 4_{1}; 5_{2} 3_{2}) \oplus (2_{2} 1_{1} 5_{1} 4_{2}; 5_{1} 3_{1}) \oplus (2_{1} 5_{2} 4_{2} 3_{2}; 4_{2} 1_{2}) \oplus \\ (2_{2} 5_{1} 4_{1} 3_{1}; 4_{1} 1_{1})} . \end{aligned}$ $\begin{aligned} E_{2} (K_{6}) = & {(1_{2} 2_{1} 6_{2} 3_{2}; 6_{2} 4_{1}) \oplus (1_{1} 6_{2} 3_{1} 2_{1}; 3_{1} 5_{1}) \oplus (3_{2} 5_{2} 2_{2} 4_{1}; 2_{2} 6_{2}) \oplus \\ (1_{2} 5_{1} 3_{2} 2_{2}; 3_{2} 4_{2}) \oplus (2_{1} 5_{2} 3_{1} 4_{1}; 3_{1} 1_{2}) \oplus (2_{1} 4_{2} 5_{2} 6_{2}; 5_{2} 1_{2}) \oplus (4_{1} 5_{1} 2_{2} 6_{1}; 2_{2} 1_{1}) \oplus \\ (2_{1} 6_{1} 1_{1} 4_{1}; 1_{1} 3_{1}) \oplus (2_{2} 4_{2} 5_{1} 6_{1}; 5_{1} 1_{1}) \oplus (3_{2} 4_{1} 5_{2} 6_{1}; 5_{2} 1_{1}) \oplus (5_{1} 2_{1} 1_{1} 4_{2}; 1_{1} 3_{2}) \oplus \\ (3_{1} 2_{2} 1_{2} 4_{2}; 1_{2} 6_{1}) \oplus (3_{1} 6_{1} 4_{1} 1_{2}; 4_{1} 2_{1}) \oplus (3_{1} 4_{2} 6_{2} 5_{1}; 6_{2} 1_{2}) \oplus (4_{2} 6_{1} 3_{2} 2_{1}; 3_{2} 1_{2})} . \end{aligned}$ $\begin{aligned} E_{2} (K_{7}) = & {(3_{1} 2_{1} 1_{1} 6_{1}; 1_{1} 4_{2}) \oplus (4_{2} 7_{1} 6_{1} 5_{1}; 6_{1} 1_{2}) \oplus (2_{1} 7_{2} 6_{2} 5_{1}; 6_{2} 4_{1}) \oplus \\ (1_{2} 7_{1} 6_{2} 5_{2}; 6_{2} 2_{2}) \oplus (1_{2} 2_{1} 6_{1} 5_{2}; 6_{1} 4_{1}) \oplus (2_{1} 7_{1} 5_{1} 3_{1}; 5_{1} 4_{2}) \oplus (1_{1} 7_{2} 5_{2} 4_{2}; 5_{2} 2_{1}) \oplus \\ (2_{2} 4_{2} 6_{2} 3_{1}; 6_{2} 1_{2}) \oplus (7_{1} 3_{2} 5_{1} 4_{1}; 5_{1} 2_{2}) \oplus (2_{2} 7_{1} 5_{2} 4_{1}; 5_{2} 1_{1}) \oplus (7_{1} 4_{1} 1_{1} 2_{2}; 1_{1} 5_{1}) \oplus \\ (3_{2} 5_{2} 1_{2} 2_{2}; 1_{2} 4_{2}) \oplus (4_{2} 3_{2} 7_{2} 6_{1}; 7_{2} 5_{1}) \oplus (2_{2} 5_{2} 3_{1} 1_{2}; 3_{1} 4_{1}) \oplus (4_{1} 2_{1} 3_{2} 6_{1}; 3_{2} 1_{2}) \oplus \\ (4_{2} 2_{1} 6_{2} 3_{2}; 6_{2} 1_{1}) \oplus (2_{1} 5_{1} 1_{2} 7_{2}; 1_{2} 4_{1}) \oplus (4_{2} 7_{2} 3_{1} 1_{1}; 3_{1} 6_{1}) \oplus (4_{2} 6_{1} 2_{2} 3_{2}; 2_{2} 7_{2}) \oplus \\ (1_{1} 3_{2} 4_{1} 7_{2}; 4_{1} 2_{2}) \oplus (1_{1} 7_{1} 3_{1} 2_{2}; 3_{1} 4_{2})} . \end{aligned}$

Lemma 2.11. A gregarious

Y_{5}

tree decomposition for each graph

G

\in

G

=

{K_{i}}

is admissible in

E_{2} (K_{i})

, for all

i \in {10, 11, 12, 13, 14, 15, 18}

Proof. A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{i})$ , $i \in {10, 11, 12, 13, 14, 15, 18}$ can be derived as follows:

Let $K_{10}$ $=$ $K_{7}$ $\oplus$ $K_{10} ∖ K_{7}$ . We then write $E_{2} (K_{10})$ $=$ $E_{2} (K_{7}) \oplus E_{2} (K_{10} ∖ K_{7})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{10} ∖ K_{7})$ and $E_{2} (K_{7})$ have been respectively derived in Lemmas 2.9 and 2.10. A gregarious $Y_{5}$ tree decomposition has been found for $E_{2} (K_{10})$ .
Let $K_{11}$ $=$ $K_{6}$ $\oplus$ $K_{11} ∖ K_{6}$ . We then write $E_{2} (K_{11})$ $=$ $E_{2} (K_{6})$ $\oplus$ $E_{2} (K_{11} ∖ K_{6})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{11} ∖ K_{6})$ and $E_{2} (K_{6})$ have been respectively derived in Lemmas 2.9 and 2.10. Hence, we concluded that, $E_{2} (K_{11})$ has a gregarious $Y_{5}$ tree decomposition.
Let $K_{12}$ $=$ $K_{5}$ $\oplus$ $K_{12} ∖ K_{5}$ . We then write $E_{2} (K_{12})$ $=$ $E_{2} (K_{5})$ $\oplus$ $E_{2} (K_{12} ∖ K_{5})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{12} ∖ K_{5})$ and $E_{2} (K_{5})$ have been respectively derived in Lemmas 2.9 and 2.10. Our conclusion was that, $E_{2} (K_{12})$ has a gregarious $Y_{5}$ tree decomposition.
Let $K_{13}$ $=$ $K_{5}$ $\oplus$ $K_{13} ∖ K_{5}$ . We then write $E_{2} (K_{13})$ $=$ $E_{2} (K_{5})$ $\oplus$ $E_{2} (K_{13} ∖ K_{5})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{13} ∖ K_{5})$ and $E_{2} (K_{5})$ have been respectively derived in Lemmas 2.9 and 2.10. A gregarious $Y_{5}$ tree decomposition is obtained for $E_{2} (K_{13})$ .
Let $K_{14}$ $=$ $K_{6}$ $\oplus$ $K_{14} ∖ K_{6}$ . We then write $E_{2} (K_{14})$ $=$ $E_{2} (K_{6})$ $\oplus$ $E_{2} (K_{14} ∖ K_{6})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{14} ∖ K_{5})$ and $E_{2} (K_{6})$ have been respectively derived in Lemmas 2.9 and 2.10. Consequently, $E_{2} (K_{14})$ is decomposed into a gregarious $Y_{5}$ tree.
Let $K_{15}$ $=$ $K_{7}$ $\oplus$ $K_{15} ∖ K_{7}$ . We then write $E_{2} (K_{15})$ $=$ $E_{2} (K_{7})$ $\oplus$ $E_{2} (K_{15} ∖ K_{7})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{15} ∖ K_{7})$ and $E_{2} (K_{7})$ have been respectively derived in Lemmas 2.9 and 2.10. A gregarious $Y_{5}$ tree decomposition has been found for $E_{2} (K_{15})$ .
Let $K_{18}$ $=$ 3 $K_{6}$ $\oplus$ $K_{6, 6, 6}$ . We then write $E_{2} (K_{18})$ $=$ 3 $E_{2} (K_{6})$ $\oplus$ $E_{2} (K_{6, 6, 6})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{6, 6, 6})$ and $E_{2} (K_{6})$ have been respectively derived in Lemmas 2.5 and 2.10. A gregarious $Y_{5}$ tree decomposition has been found for $E_{2} (K_{18})$ .

For $E_{2} (K_{i})$ , $i \in {10, 11, 12, 13, 14, 15, 18}$ , a gregarious $Y_{5}$ tree decomposition was obtained from (1) – (7).

Lemma 2.12. A gregarious

Y_{5}

tree decomposition for each graph

G

\in

G

=

{K_{i}}

is admissible in

E_{2} (K_{i})

, for all

i \in {19, 20, 29, 30, 31, 34, 35, 36}

Proof. A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{i})$ , $i \in {19, 20, 29, 30, 31, 34, 35, 36}$ can be derived as follows:

Let $K_{19}$ $=$ $K_{14}$ $\oplus$ $K_{19} ∖ K_{14}$ . We then write $E_{2} (K_{19})$ $=$ $E_{2} (K_{14})$ $\oplus$ $E_{2} (K_{19} ∖ K_{14})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{19} ∖ K_{14})$ and $E_{2} (K_{14})$ have been respectively derived in Lemmas 2.9 and 2.11. A gregarious $Y_{5}$ tree decomposition has been found for $E_{2} (K_{19})$ .
Let $K_{20}$ $=$ $K_{13}$ $\oplus$ $K_{20} ∖ K_{13}$ . We then write $E_{2} (K_{20})$ $=$ $E_{2} (K_{13})$ $\oplus$ $E_{2} (K_{20} ∖ K_{13})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{20} ∖ K_{13})$ and $E_{2} (K_{13})$ have been respectively derived in Lemmas 2.9 and 2.11. Hence, we concluded that, $E_{2} (K_{20})$ has a gregarious $Y_{5}$ tree decomposition.
Let $K_{29}$ $=$ $K_{20}$ $\oplus$ $K_{29} ∖ K_{20}$ . We then write $E_{2} (K_{29})$ $=$ $E_{2} (K_{20})$ $\oplus$ $E_{2} (K_{29} ∖ K_{20})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{29} ∖ K_{20})$ and $E_{2} (K_{20})$ have been respectively derived in Lemma 2.9 and in the above Case 2. Our conclusion was that, $E_{2} (K_{29})$ has a gregarious $Y_{5}$ tree decomposition.
Let $K_{30}$ $=$ 3 $K_{10}$ $\oplus$ $K_{10, 10, 10}$ . We then write $E_{2} (K_{30})$ $=$ 3 $E_{2} (K_{10})$ $\oplus$ $E_{2} (K_{10, 10, 10})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{10})$ and $E_{2} (K_{10, 10, 10})$ have been respectively derived in Lemmas 2.11 and 2.5. A gregarious $Y_{5}$ tree decomposition is obtained for $E_{2} (K_{30})$ .
Let $K_{31}$ $=$ 2 $K_{12}$ $\oplus$ $K_{7}$ $\oplus$ $K_{12, 12, 7}$ . We then write $E_{2} (K_{31})$ $=$ 2 $E_{2} (K_{12})$ $\oplus$ $E_{2} (K_{7})$ $\oplus$ $E_{2} (K_{12, 12, 7})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{7})$ , $E_{2} (K_{12})$ and $E_{2} (K_{12, 12, 7})$ have been respectively derived in Lemmas 2.10, 2.11 and 2.8. Consequently, $E_{2} (K_{31})$ is decomposed into a gregarious $Y_{5}$ tree.
Let $K_{34}$ $=$ 2 $K_{12}$ $\oplus$ $K_{10}$ $\oplus$ $K_{12, 12, 10}$ . We then write $E_{2} (K_{34})$ $=$ 2 $E_{2} (K_{12})$ $\oplus$ $E_{2} (K_{10})$ $\oplus$ $E_{2} (K_{12, 12, 10})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{10})$ , $E_{2} (K_{12})$ and $E_{2} (K_{12, 12, 10})$ have been derived in Lemmas 2.11 and 2.8. A gregarious $Y_{5}$ tree decomposition has been found for $E_{2} (K_{34})$ .
Let $K_{35}$ $=$ $K_{30}$ $\oplus$ $K_{35} ∖ K_{30}$ . We then write $E_{2} (K_{35})$ $=$ $E_{2} (K_{30})$ $\oplus$ $E_{2} (K_{35} ∖ K_{30})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{35} ∖ K_{30})$ and $E_{2} (K_{30})$ have been respectively derived in Lemma 2.9 and in the above Case 4. A gregarious $Y_{5}$ tree decomposition has been found for $E_{2} (K_{35})$ .
Let $K_{36}$ $=$ 3 $K_{12}$ $\oplus$ $K_{12, 12, 12}$ . Then, we write $E_{2} (K_{36})$ $=$ 3 $E_{2} (K_{12})$ $\oplus$ $E_{2} (K_{12, 12, 12})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{12})$ and $E_{2} (K_{12, 12, 12})$ have been respectively derived in Lemmas 2.11 and 2.5. A gregarious $Y_{5}$ tree decomposition has been found for $E_{2} (K_{36})$ .

For $E_{2} (K_{i})$ , $i \in {19, 20, 29, 30, 31, 34, 35, 36}$ , a gregarious $Y_{5}$ tree decomposition was obtained from (1) – (8).

Note 2.13. Further, in order to prove

K_{m} (n)

has a gregarious

Y_{5}

tree decomposition when

m \equiv 5, 6, 7, 10, 11, 12 (\mod 8)

and

n

is even, it is enough to prove that

K_{m} (2)

admits a gregarious

Y_{5}

tree decomposition. It is clearly stated in Lemma 2.3.

Lemma 2.14. A gregarious

Y_{5}

tree decomposition is admissible in

K_{m} (2)

when

m \equiv a (\mod 8)

a \in {5, 6, 7, 10, 11, 12}

Proof. Consider the graph $K_{m} (2)$ $≃$ $E_{2} (K_{m})$ and let $m = 8 s + a$ , $a \in {5, 6, 7, 10, 11, 12}$ .

A non negative integer $s$ can be categorized into 4 Cases: (i) $s \equiv 0, 2 (\mod 6)$ , (ii) $s \equiv 4 (\mod 6)$ , (iii) $s \equiv 1, 5 (\mod 6)$ and (iv) $s \equiv 3 (\mod 6)$ .

Case i: For $s \equiv 0, 2 (\mod 6)$ , the graph $K_{m}$ decomposes as a copy of $K_{a}$ , $s$ copies of $K_{8}$ , $\frac{s}{2}$ copies of $K_{8, 8, a}$ and $\frac{s^{2} - 2 s}{6}$ copies of $K_{8, 8, 8}$ . Therefore, $E_{2} (K_{m})$ $=$ $E_{2} (K_{a} \oplus s K_{8} \oplus \frac{s}{2} K_{8, 8, a} \oplus \frac{s^{2} - 2 s}{6} K_{8, 8, 8})$ $=$ $E_{2} (K_{a})$ $\oplus$ $s E_{2} (K_{8})$ $\oplus$ $\frac{s}{2} E_{2} (K_{8, 8, a})$ $\oplus$ $\frac{s^{2} - 2 s}{6} E_{2} (K_{8, 8, 8})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{a})$ and $E_{2} (K_{8})$ have been obtained from the Lemmas 2.10, 2.11 and 2.4. Further more, the Lemma 2.5 has yielded a gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{8, 8, 8})$ . Also, the Lemmas 2.6 and 2.7 have been used to obtain a gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{8, 8, a})$ . Consequently, it proves that a gregarious $Y_{5}$ tree decomposition exists for $E_{2} (K_{m})$ .

Case ii: For $s \equiv 4 (\mod 6)$ , the graph $K_{m}$ decomposes as a copy of $K_{a}$ , $s - 4$ copies of $K_{8}$ , $\frac{s}{2}$ copies of $K_{8, 8, a}$ , $\frac{s^{2} - 2 s - 8}{6}$ copies of $K_{8, 8, 8}$ and 4 copies of $K_{16} ∖ K_{8}$ . Therefore, $E_{2} (K_{m})$ $=$ $E_{2} (K_{a} \oplus (s - 4) K_{8} \oplus \frac{s}{2} K_{8, 8, a} \oplus \frac{s^{2} - 2 s - 8}{6} K_{8, 8, 8} \oplus 4 (K_{16} ∖ K_{8}))$ $=$ $E_{2} (K_{a})$ $\oplus$ $(s - 4) E_{2} (K_{8})$ $\oplus$ $\frac{s}{2} E_{2} (K_{8, 8, a})$ $\oplus$ $\frac{s^{2} - 2 s - 8}{6} E_{2} (K_{8, 8, 8})$ $\oplus$ $4 E_{2} (K_{16} ∖ K_{8})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{8, 8, 8})$ have been obtained from the Lemma 2.5. Further more, a gregarious $Y_{5}$ tree decomposition have been obtained for $E_{2} (K_{8, 8, a})$ from the Lemmas 2.6 and 2.7 Also, a gregarious $Y_{5}$ tree decomposition have been obtained for $E_{2} (K_{16} ∖ K_{8})$ from the Lemma 2.9. In addition with, a gregarious $Y_{5}$ tree decomposition have been obtained for $E_{2} (K_{a})$ and $E_{2} (K_{8})$ from the Lemmas 2.10, 2.11 and 2.4. Consequently, it proves that a gregarious $Y_{5}$ tree decomposition exists for $E_{2} (K_{m})$ .

Case iii: For $s \equiv 1, 5 (\mod 6)$ , the graph $K_{m}$ decomposes as a copy of $K_{a + 8}$ , $\frac{s - 1}{2}$ copies of $K_{16}$ , $\frac{s - 1}{2}$ copies of $K_{8, 8, a}$ and $\frac{s^{2} - 3 s + 2}{6}$ copies of $K_{8, 8, 8}$ . Therefore, $E_{2} (K_{m})$ $=$ $E_{2} (K_{a + 8} \oplus \frac{s - 1}{2} K_{16} \oplus \frac{s - 1}{2} K_{8, 8, a} \oplus \frac{s^{2} - 3 s + 2}{6} K_{8, 8, 8})$ $=$ $E_{2} (K_{a + 8})$ $\oplus$ $\frac{s - 1}{2} E_{2} (K_{16})$ $\oplus$ $\frac{s - 1}{2} E_{2} (K_{8, 8, a})$ $\oplus$ $\frac{s^{2} - 3 s + 2}{6} E_{2} (K_{8, 8, 8})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{8, 8, 8})$ have been obtained from the Lemma 2.5. Further more, a gregarious $Y_{5}$ tree decomposition have been obtained for $E_{2} (K_{8, 8, a})$ from the Lemmas 2.6 and 2.7. Also, a gregarious $Y_{5}$ tree decomposition have been obtained for $E_{2} (K_{a + 8})$ from the Lemmas 2.11 and 2.12. In addition with, a gregarious $Y_{5}$ tree decomposition have been obtained for $E_{2} (K_{16})$ from the Lemma 2.4. Consequently, it proves that a gregarious $Y_{5}$ tree decomposition exists for $E_{2} (K_{m})$ .

Case iv: For $s \equiv 3 (\mod 6)$ , the graph $K_{m}$ decomposes as a copy of $K_{a + 24}$ , $\frac{s - 3}{2}$ copies of $K_{16}$ , $\frac{s - 3}{2}$ copies of $K_{8, 8, a}$ and $\frac{s^{2} - 3 s}{6}$ copies of $K_{8, 8, 8}$ . Therefore, $E_{2} (K_{m})$ $=$ $E_{2} (K_{a + 24} \oplus \frac{s - 3}{2} K_{16} \oplus \frac{s - 3}{2} K_{8, 8, a} \oplus \frac{s^{2} - 3 s}{6} K_{8, 8, 8})$ $=$ $E_{2} (K_{a + 24})$ $\oplus$ $\frac{s - 3}{2} E_{2} (K_{16})$ $\oplus$ $\frac{s - 3}{2} E_{2} (K_{8, 8, a})$ $\oplus$ $\frac{s^{2} - 3 s}{6} E_{2} (K_{8, 8, 8})$ . A gregarious $Y_{5}$ tree decomposition for $E_{2} (K_{8, 8, 8})$ have been obtained from the Lemma 2.5. Further more, a gregarious $Y_{5}$ tree decomposition have been obtained for $E_{2} (K_{8, 8, a})$ from the Lemmas 2.6 and 2.7. Also, a gregarious $Y_{5}$ tree decomposition have been obtained for $E_{2} (K_{a + 24})$ from the Lemma 2.12. In addition with, a gregarious $Y_{5}$ tree decomposition have been obtained for $E_{2} (K_{16})$ from the Lemma 2.4. Consequently, it proves that a gregarious $Y_{5}$ tree decomposition exists for $E_{2} (K_{m})$ .

The Cases (i) – (iv) mentioned earlier will provide a gregarious $Y_{5}$ tree decomposition for $K_{m} (2)$ .

Theorem 2.15. The occurence of a gregarious

Y_{5}

tree decomposition for

K_{m} (n)

is possible only if

n^{2} m (m - 1) \equiv 0 (\mod 8)

Proof. Necessity: Given that $∣ E (K_{m} (n)) ∣$ $=$ $\frac{n^{2} m (m - 1)}{2}$ and $∣ E (Y_{5}) ∣= 4$ . To determine a gregarious $Y_{5}$ tree decomposition for $K_{m} (n)$ , the necessary condition for edge divisibility has been expressed as $\frac{∣ E (K_{m} (n) ∣}{∣ E (Y_{5}) ∣}$ $=$ $\frac{n^{2} m (m - 1)}{2 \times 4}$ . That is, $8 | n^{2} m (m - 1)$ . It can be written as $n^{2} m (m - 1) \equiv 0 (\mod 8)$ .

Sufficiency: The occurence of a gregarious $Y_{5}$ tree decomposition for $K_{m} (n)$ has been described in Lemmas 2.4 and 2.14.

3. Conclusion

In this document, we present a complete and detailed solution to the problem of identifying the presence of a gregarious $Y_{5}$ tree decomposition in $K_{m} (n)$ . Decomposing $K_{m} (n)$ into a $Y_{k}$ tree (gregarious $Y_{k}$ tree) is generally a challanging task for $k \geq 6$ .

References:

J. Barát and D. Gerbner. Edge-decomposition of graphs into copies of a tree with four edges. arXiv preprint arXiv:1203.1671, 2012. https://doi.org/10.48550/arXiv.1203.1671.
J.-C. Bermond, C. Huang, A. Rosa, and D. Sotteau. Decomposition of complete graphs into isomorphic subgraphs with five vertices. Ars combinatoria, 10:211–254, 1980.
G. Ding, T. Johnson, and P. Seymour. Spanning trees with many leaves. Journal of Graph Theory, 37(4):189–197, 2001. http://dx.doi.org/10.1002/jgt.1013.
M. Drmota and A. Lladó. Almost every tree with m edges decomposes k_{2m, 2m}. Combinatorics, Probability and Computing, 23(1):50–65, 2014. https://doi.org/10.1017/S0963548313000485.
A. T. Elakkiya and A. Muthusamy. Gregarious kite decomposition of tensor product of complete graphs. Electronic Notes in Discrete Mathematics, 53:83–96, 2016. https://doi.org/10.1016/j.endm.2016.05.008.
A. T. Elakkiya and A. Muthusamy. Gregarious kite factorization of tensor product of complete graphs. Discussiones Mathematicae Graph Theory, 40(1):7–24, 2020.
C.-M. Fu, Y.-F. Hsu, S.-W. Lo, and W.-C. Huang. Some gregarious kite decompositions of complete equipartite graphs. Discrete Mathematics, 313(5):726–732, 2013. https://doi.org/10.1016/j.disc.2012.10.017.
S. Gomathi and A. Tamil Elakkiya. Gregarious Y5-tree decompositions of tensor product of complete graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 117:185–194, 2023. http://dx.doi.org/10.61091/jcmcc117-17.
G. Haggard and P. McWha. Decomposition of complete graphs into trees. Czechoslovak Mathematical Journal, 25(1):31–36, 1975.
C. Huang and A. Rosa. Decomposition of complete graphs into trees. Ars Combin, 5:23–63, 1978.
M. S. Jacobson, M. Truszczyński, and Z. Tuza. Decompositions of regular bipartite graphs. Discrete Mathematics, 89(1):17–27, 1991. https://doi.org/10.1016/0012-365X(91)90396-J.
K. F. Jao, A. V. Kostochka, and D. B. West. Decomposition of cartesian products of regular graphs into isomorphic trees. Journal of Combinatorics, 4(4):469–490, 2013.
A. Lladó. Almost every tree with n edges decomposes k_{2n, 2n}. Electronic Notes in Discrete Mathematics, 38:571–574, 2011. https://doi.org/10.1016/j.endm.2011.09.093.
A. Lladó and S.-C. López. Edge-decompositions of k_{n, n} into isomorphic copies of a given tree. Journal of Graph Theory, 48(1):1–18, 2005. https://doi.org/10.1002/jgt.20024.
R. Montgomery, A. Pokrovskiy, and B. Sudakov. A proof of Ringel’s conjecture. Geometric and Functional Analysis, 31(3):663–720, 2021. https://doi.org/10.1007/s00039-021-00576-2.
R. L. Ringel and M. D. Steer. Some effects of tactile and auditory alterations on speech output. Journal of Speech and Hearing Research, 6(4):369–378, 1963.
J. Siemons. Surveys in combinatorics, 1989: Invited papers at the Twelfth British Combinatorial Conference, 12, 1989.

[1] J. Barát and D. Gerbner. Edge-decomposition of graphs into copies of a tree with four edges. arXiv preprint arXiv:1203.1671, 2012. https://doi.org/10.48550/arXiv.1203.1671.

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

[3] G. Ding, T. Johnson, and P. Seymour. Spanning trees with many leaves. Journal of Graph Theory, 37(4):189–197, 2001. http://dx.doi.org/10.1002/jgt.1013.

[4] M. Drmota and A. Lladó. Almost every tree with m edges decomposes k_{2m, 2m}. Combinatorics, Probability and Computing, 23(1):50–65, 2014. https://doi.org/10.1017/S0963548313000485.

[5] A. T. Elakkiya and A. Muthusamy. Gregarious kite decomposition of tensor product of complete graphs. Electronic Notes in Discrete Mathematics, 53:83–96, 2016. https://doi.org/10.1016/j.endm.2016.05.008.

[6] A. T. Elakkiya and A. Muthusamy. Gregarious kite factorization of tensor product of complete graphs. Discussiones Mathematicae Graph Theory, 40(1):7–24, 2020.

[7] C.-M. Fu, Y.-F. Hsu, S.-W. Lo, and W.-C. Huang. Some gregarious kite decompositions of complete equipartite graphs. Discrete Mathematics, 313(5):726–732, 2013. https://doi.org/10.1016/j.disc.2012.10.017.

[8] S. Gomathi and A. Tamil Elakkiya. Gregarious Y5-tree decompositions of tensor product of complete graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 117:185–194, 2023. http://dx.doi.org/10.61091/jcmcc117-17.

[9] G. Haggard and P. McWha. Decomposition of complete graphs into trees. Czechoslovak Mathematical Journal, 25(1):31–36, 1975.

[10] C. Huang and A. Rosa. Decomposition of complete graphs into trees. Ars Combin, 5:23–63, 1978.

[11] M. S. Jacobson, M. Truszczyński, and Z. Tuza. Decompositions of regular bipartite graphs. Discrete Mathematics, 89(1):17–27, 1991. https://doi.org/10.1016/0012-365X(91)90396-J.

[12] K. F. Jao, A. V. Kostochka, and D. B. West. Decomposition of cartesian products of regular graphs into isomorphic trees. Journal of Combinatorics, 4(4):469–490, 2013.

[13] A. Lladó. Almost every tree with n edges decomposes k_{2n, 2n}. Electronic Notes in Discrete Mathematics, 38:571–574, 2011. https://doi.org/10.1016/j.endm.2011.09.093.

[14] A. Lladó and S.-C. López. Edge-decompositions of k_{n, n} into isomorphic copies of a given tree. Journal of Graph Theory, 48(1):1–18, 2005. https://doi.org/10.1002/jgt.20024.

[15] R. Montgomery, A. Pokrovskiy, and B. Sudakov. A proof of Ringel’s conjecture. Geometric and Functional Analysis, 31(3):663–720, 2021. https://doi.org/10.1007/s00039-021-00576-2.

[16] R. L. Ringel and M. D. Steer. Some effects of tactile and auditory alterations on speech output. Journal of Speech and Hearing Research, 6(4):369–378, 1963.

[17] J. Siemons. Surveys in combinatorics, 1989: Invited papers at the Twelfth British Combinatorial Conference, 12, 1989.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

Decomposition of a complete equipartite graph into gregarious $Y_{5}$ Tree

Abstract

1. Introduction

2. Gregarious $Y_{5}$ tree decomposition of $K_{m} (n)$

3. Conclusion

References:

Information

Guidelines

CP Initiatives

Follow CP

1	2	3	4	5	6	7	8
2	3	4	5	6	7	8	1
3	4	5	6	7	8	1	2
4	5	6	7	8	1	2	3
5	6	7	8	1	2	3	4
6	7	8	1	2	3	4	5
7	8	1	2	3	4	5	6
8	1	2	3	4	5	6	7

1	2	3	4	5	6	7	8	9	10	11	12
2	3	4	5	6	7	8	9	10	11	12	1
3	4	5	6	7	8	9	10	11	12	1	2
4	5	6	7	8	9	10	11	12	1	2	3
5	6	7	8	9	10	11	12	1	2	3	4
6	7	8	9	10	11	12	1	2	3	4	5
7	8	9	10	11	12	1	2	3	4	5	6
8	9	10	11	12	1	2	3	4	5	6	7
9	10	11	12	1	2	3	4	5	6	7	8
10	11	12	1	2	3	4	5	6	7	8	9
11	12	1	2	3	4	5	6	7	8	9	10
12	1	2	3	4	5	6	7	8	9	10	11

1	2	3	4	5	6	7	8
2	3	4	5	6	7	8	1
3	4	5	6	7	8	1	2
4	5	6	7	8	1	2	3
5	6	7	8	1	2	3	4
6	7	8	1	2	3	4	5
7	8	1	2	3	4	5	6
8	1	2	3	4	5	6	7

1	2	3	4	5	6	7	8	9	10	11	12
2	3	4	5	6	7	8	9	10	11	12	1
3	4	5	6	7	8	9	10	11	12	1	2
4	5	6	7	8	9	10	11	12	1	2	3
5	6	7	8	9	10	11	12	1	2	3	4
6	7	8	9	10	11	12	1	2	3	4	5
7	8	9	10	11	12	1	2	3	4	5	6
8	9	10	11	12	1	2	3	4	5	6	7
9	10	11	12	1	2	3	4	5	6	7	8
10	11	12	1	2	3	4	5	6	7	8	9
11	12	1	2	3	4	5	6	7	8	9	10
12	1	2	3	4	5	6	7	8	9	10	11

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

Decomposition of a complete equipartite graph into gregarious Y5 Tree

Abstract

1. Introduction

2. Gregarious Y5 tree decomposition of Km(n)

3. Conclusion

References:

Information

Guidelines

CP Initiatives

Follow CP

Decomposition of a complete equipartite graph into gregarious $Y_{5}$ Tree

2. Gregarious $Y_{5}$ tree decomposition of $K_{m} (n)$

1	2	3	4	5	6	7	8
2	3	4	5	6	7	8	1
3	4	5	6	7	8	1	2
4	5	6	7	8	1	2	3
5	6	7	8	1	2	3	4
6	7	8	1	2	3	4	5
7	8	1	2	3	4	5	6
8	1	2	3	4	5	6	7

1	2	3	4	5	6	7	8	9	10	11	12
2	3	4	5	6	7	8	9	10	11	12	1
3	4	5	6	7	8	9	10	11	12	1	2
4	5	6	7	8	9	10	11	12	1	2	3
5	6	7	8	9	10	11	12	1	2	3	4
6	7	8	9	10	11	12	1	2	3	4	5
7	8	9	10	11	12	1	2	3	4	5	6
8	9	10	11	12	1	2	3	4	5	6	7
9	10	11	12	1	2	3	4	5	6	7	8
10	11	12	1	2	3	4	5	6	7	8	9
11	12	1	2	3	4	5	6	7	8	9	10
12	1	2	3	4	5	6	7	8	9	10	11