A \(\mathcal{Y}\) tree on \(k\) vertices is denoted by \(\mathcal{Y}_k\). To decompose a graph into \(\mathcal{Y}_k\) trees, it is necessary to create a collection of subgraphs that are isomorphic to \(\mathcal{Y}_k\) tree and are all distinct. It is possible to acquire the necessary condition to decompose \(K_m(n)\) into \(\mathcal{Y}_k\) trees (\(k \geq 5\)), which has been obtained as \(n^2m(m-1) \equiv 0 \pmod{2(k-1)}\). It has been demonstrated in this document that, a gregarious \(\mathcal{Y}_5\) tree decomposition in \(K_m(n)\) is possible only if \(n^2m(m-1) \equiv 0 \pmod{8}\).
To create a \(\mathcal{Y}_k\) tree \((v_1\,\,v_2\,\,\ldots\,\,v_{k-1}; v_{k-2}\,\,v_k)\), its edges are represented as \(\{(v_1v_2, v_2v_3,\ldots, v_{k-2}v_{k-1})\cup (v_{k-2}v_k)\}\) while the vertices are represented as \(\{v_1,\,v_2,\ldots,\,v_k\}\). A \(\mathcal{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)\mid u \in V(G),v \in V(H)\}\) and \(E(G \otimes H)\) \(=\) \(\{(u,v)(x,y)\mid u = x\) and \(vy \in E(H)\), or \(ux \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\mid p\in V(G), q \in I_r\}\) and \(E(G \otimes I_r)\) \(=\) \(\{p_q s_t \mid ps \in E(G)\) and \(q,t\in I_r\}\). To make it easier for us, the extented graph is denoted by \(\mathcal{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 \(\mathcal{E}_r(K_m(n))\) can be considered as the extended graph \(\mathcal{E}_{nr}(K_m)\), ie., \(K_m(nr)\).
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 \(\mathcal{H}\), then \(G\) is said to decompose into \(\mathcal{H}\).
However, a \(\mathcal{Y}_5\) tree decomposition in \(\mathcal{E}_r(G)\) is termed as gregarious, if for every \(\mathcal{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 \(\mathcal{Y}_5\) tree decomposition when \(m \equiv 0,1 \pmod 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_{2m+1}\) has been decomposed into a tree with precisely \(m\) edges. \(Ja^{'}nos\) \(Bara^{'}t\) and \(Da^{'}niel\) \(Gerbner\) [1] show that 191-edge connected graph admits a \(\mathcal{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 \(mn(m-1)(n-1) \equiv 0 \pmod 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 \(mn \equiv 0 \pmod 4\) and \((m-1)(n-1)\equiv 0 \pmod 2\) are present. A kite decomposition for \(K_m(n)\) is gregarious is not possible unless \(m \equiv 0,1 \pmod 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 \(\mathcal{Y}_5\) tree decomposition for \(K_m \times K_n\), stating that this decomposition exists only if \(mn(m-1)(n-1) \equiv 0 \pmod 8\) is present.
Our main concern is, to decompose a complete equipartite graph as gregarious \(\mathcal{Y}_5\) trees. This paper proves that a gregarious \(\mathcal{Y}_5\) tree decomposition for \(K_m(n)\) is only possible if \(n^2m(m-1)\equiv 0 \pmod {8}\). By the notion of a gregarious \(\mathcal{Y}_5\) tree decomposition, the number of partite sets must be at least \(5 \,\,(m\geq5)\). Moreover, a gregarious \(\mathcal{Y}_5\) tree decomposition for \(K_m(n)\) falls on the following cases:
\(m \equiv 0,1 \pmod 8\), for all \(n\), \(n\geq2\).
\(m \equiv 5,6,7,10,11,12 \pmod 8\), for even \(n\).
To establish our key result, the following result is necessary:
(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_{ij}}\,\,\,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.
| \(\fbox1\) | 2 | \(\fbox3\) | 4 |
| 2 | 3 | 4 | 1 |
| \(\fbox3\) | 4 | \(\fbox1\) | 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 \(\mathcal{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 \(\mathcal{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)\).
Proof. By taking \(V(\mathcal{E}_r(\mathcal{Y}_5))\) \(=\) \(\{\bigcup\limits_{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_{ij}}\,\,4_i; 3_{a_{ij}}\,\,5_j\}, 1\leq i,j\leq r\), \(r\geq2\), provides a gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_r(\mathcal{Y}_5)\). ◻
Proof. If there is a collection \(\mathcal{S}\) of \(\mathcal{Y}_5\) trees in the decomposition of \(H\), then by applying Lemma 2.2 to each \(\mathcal{Y}_5 \in \mathcal{S}\), we will get a gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_r(\mathcal{Y}_5)\). Consequently, we can attain a gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_r(H)\), \(r\geq2\). ◻
Proof. In Theorem 1.1, stating that, \(\mathcal{Y}_5\) tree decomposition is possible for \(K_m\) when \(m\equiv0,1\pmod 8\). Thus, according to the Lemma 2.3, we can attain a gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_r(K_m)\), \(r\geq2\). ◻
Proof. Let us consider \(V(K_{2,\,2,\,2})= \{\bigcup\limits_{p=1}^3 p_q,1\leq q \leq 2\}\). The set given below contains a \(\mathcal{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 \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_r(K_{2,\,2,\,2})\) if \(r = 3,4,5,6\), according to the Lemma 2.3. That is, a gregarious \(\mathcal{Y}_5\) tree decomposition exists for the graphs \(\mathcal{G}\) \(=\) \(\{K_{6,\,6,\,6}, K_{8,\,8,\,8}, K_{10,\,10,\,10}, K_{12,\,12,\,12}\}\), since \(\mathcal{E}_r(K_m(n))\) \(\simeq\) \(K_m(nr)\). Moreover, by repeating the same process to each graph \(G\) \(\in\) \(\mathcal{G}\), we can acquire a gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(G)\). ◻
Proof. (1) A gregarious \(\mathcal{Y}_5\) tree decomposition for
\(\mathcal{E}_2(K_{8,\,8,\,5})\) can be
derived as follows:
Let \(V(K_{8,\,8,\,5})\) \(=\) \(\{(\bigcup\limits_{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 \(\mathcal{S}_1\) of
\(\mathcal{Y}_5\) tree decomposition
for \(K_{8,\,8,\,5}\) as follows:
| 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 | \(\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\) |
\(\bullet\) As discussed in Remark 2.1, if \(a_{ij} = a_{(i+h)(j+k)} = 5\) and \(a_{i(j+k)} = a_{(i+h)j} = 1\), we get the following \(\mathcal{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 \(\mathcal{Y}\) tree cells yield \(12\) copies of \(\mathcal{Y}_5\) trees, in which each are isomorphic and disjoint mutually.
\(\bullet\) For all \((i,j)\in \{(1,2),(2,1),(3,8),(4,7),(5,6),(6,5),(7,4),(8,3)\}\), we have \(a_{ij} = 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_{ij} = 3\). It is possible to obtain a \(\mathcal{Y}_5\) tree corresponding to each \((i,j)\), such as \((3_{a_{ij}}\,\,2_j\,\,1_i\,\,2_{k+6-i}; 1_i\,\,3_{k+1})\), if \(a_{ij} = k\), \(k=2,3\). Thus we may include these \(16\) disjoint copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_1\).
\(\bullet\) Similarly, for all \((i,j)\in \{(1,4),(2,3),(3,2),(4,1),(5,8),(6,7),(7,6),(8,5)\}\), \(a_{ij} = k\), \(k=4\), it is possible to obtain a \(\mathcal{Y}_5\) tree. We then place the \(8\) disjoint copies of \(\mathcal{Y}_5\) trees follows from \((3_{a_{ij}}\,\,2_j\,\,1_i\,\,2_{j+2}; 1_i\,\,3_{k-2})\) in \(\mathcal{S}_1\). All together implies a \(\mathcal{Y}_5\) tree decomposition for \(K_{8,\,8,\,5}\). As a consequence of it, a gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{8,\,8,\,5})\) may derived through the use of Lemma 2.3.
(2) A gregarious \(\mathcal{Y}_5\) tree decomposition for
\(\mathcal{E}_2(K_{8,\,8,\,6})\) can be
derived as follows:
Let \(V(K_{8,\,8,\,6})\) \(=\) \(\{(\bigcup\limits_{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 \(\mathcal{S}_2\) of \(\mathcal{Y}_5\) tree decomposition for
\(K_{8,\,8,\,6}\) as follows:
| 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\) |
\(\bullet\) As discussed in Remark 2.1, if \(a_{ij} = a_{(i+h)(j+k)}=5\) and \(a_{i(j+k)} = a_{(i+h)j}=1\), we get the following \(\mathcal{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 \(\mathcal{Y}\) tree cells yield \(12\) copies of \(\mathcal{Y}_5\) trees, in which each are isomorphic and disjoint mutually.
\(\bullet\) As discussed in Remark 2.1, if \(a_{ij} = a_{(i+h)(j+k)}=2\) and \(a_{i(j+k)} = a_{(i+h)j}=6\), we get the following \(\mathcal{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 \(\mathcal{Y}\) tree cells yield \(12\) copies of \(\mathcal{Y}_5\) trees.
\(\bullet\) For all \((i,j)\in \{(1,3),(2,2),(3,1),(4,8),(5,7),(6,6),(7,5),(8,4)\}\), \(a_{ij} = k\), \(k=3\), it is possible to obtain a \(\mathcal{Y}_5\) tree. We then place the \(8\) copies of \(\mathcal{Y}_5\) trees follows from \((3_{a_{ij}}\,\,2_j\,\,1_i\,\,2_{k+6-i}; 1_i\,\,3_{k+1})\) in \(\mathcal{S}_2\).
\(\bullet\) For all \((i,j)\in \{(1,4),(2,3),(3,2),(4,1),(5,8),(6,7),(7,6),(8,5)\}\), \(a_{ij} = k\), \(k=4\), it is possible to obtain a \(\mathcal{Y}_5\) tree. We then place the \(8\) copies of \(\mathcal{Y}_5\) trees follows from \((3_{a_{ij}}\,\,2_j\,\,1_i\,\,2_{j+3}; 1_i\,\,3_{k-1})\) in \(\mathcal{S}_2\). All together leads a \(\mathcal{Y}_5\) tree decomposition for \(K_{8,\,8,\,6}\). As a consequence of it, a gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{8,\,8,\,6})\) may derived through use of Lemma 2.3.
(3) A gregarious \(\mathcal{Y}_5\) tree decomposition for
\(\mathcal{E}_2(K_{8,\,8,\,6})\) can be
derived as follows:
Let \(V(K_{8,\,8,\,7})\) \(=\) \(\{(\bigcup\limits_{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 \(\mathcal{S}_3\) of \(\mathcal{Y}_5\) tree decomposition for
\(K_{8,\,8,\,7}\) as per the
following:
| 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 |
\(\bullet\) Consider the set of \(\mathcal{Y}\) tree cells \(\{(a_{ij}, 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 \(\mathcal{Y}\) tree cell corresponding to each \((i,j)\). All together gives \(12\) copies of \(\mathcal{Y}\) tree cells. These \(\mathcal{Y}\) tree cells provides the following \(36\) copies of \(\mathcal{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_{ij}}\,\,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_{ij}}\,\,2_{j}\,\,3_{a_{(i+h)j}}\,\,2_{j+k}; 3_{a_{(i+h)j}}\,\,1_{i}\).
\(\bullet\) For all \((i,j)\in \{(1,4),(2,3),(3,2),(4,1)\}\), \(a_{ij} = 4\), it is possible to obtain a \(\mathcal{Y}_5\) tree. We then place the \(4\) copies of \(\mathcal{Y}_5\) trees follows from \((3_{a_{ij}}\,\,2_j\,\,1_i\,\,2_{9-i}; 1_i\,\,2_i)\) in \(\mathcal{S}_3\).
\(\bullet\) For all \((i,j)\in \{(5,8),(6,7),(7,6),(8,5)\}\), \(a_{ij} = 4\), it is possible to obtain a \(\mathcal{Y}_5\) tree. We then place the \(4\) copies of \(\mathcal{Y}_5\) trees follows from \((3_{a_{ij}}\,\,2_j\,\,1_i\,\,2_{9-i}; 1_i\,\,2_{i-4})\) in \(\mathcal{S}_3\). All together leads a \(\mathcal{Y}_5\) tree decomposition for \(K_{8,\,8,\,7}\). As a consequence of it, a gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{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 \(\mathcal{Y}_5\) tree decomposition exists for \(\mathcal{E}_2(G)\), \(G\) \(\in\) \(\mathcal{G} = \{K_{8,\,8,\,5}, K_{8,\,8,\,6}, K_{8,\,8,\,7}\}\). ◻
Proof. (1) A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{8,\,8,\,10})\) can be derived as follows:
Let \(V(K_{8,\,8,\,10})\) \(=\) \(\{(\bigcup\limits_{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 \(\mathcal{S}_1\) of \(\mathcal{Y}_5\) tree decomposition for \(K_{8,\,8,\,10}\) as follows:
\(\bullet\) As discussed in Remark 2.1, if \(a_{ij} = a_{(i+h)(j+k)}=5\) and \(a_{i(j+k)} = a_{(i+h)j}=1\), we get the following \(\mathcal{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 \(\mathcal{Y}\) tree cells yield \(12\) copies of \(\mathcal{Y}_5\) trees.
\(\bullet\) For all \((i,j)\in \{(1,2),(2,1),(3,8),(4,7),(5,6),(6,5),(7,4),(8,3)\}\), we have \(a_{ij} = 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_{ij} = 3\). It is possible to obtain a \(\mathcal{Y}_5\) tree corresponding to each \((i,j)\), such as \((3_{a_{ij}}\,\,2_j\,\,1_i\,\,\infty_k; 1_i\,\,3_{a_{ij}+1})\), if \(a_{ij} = k+1\), \(k = 1, 2\). Thus we may include these \(16\) copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_1\).
\(\bullet\) For all \((i,j)\in \{(1,4),(2,3),(3,2),(4,1),(5,8),(6,7),(7,6),(8,5)\}\), we have \(a_{ij} = 4\). It is possible to obtain a \(\mathcal{Y}_5\) tree corresponding to each \((i,j)\), such as \((3_{a_{ij}}\,\,2_j\,\,1_i\,\,3_{k+5}; 1_i\,\,3_{k-1})\), if \(a_{ij} = k+1\), \(k = 3\). Thus we may include these \(8\) copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_1\).
\(\bullet\) For all \((i,j)\in \{(1,6),(2,5),(3,4),(4,3)\}\), we have \(a_{ij} = 6\). It is possible to obtain a \(\mathcal{Y}_5\) tree corresponding to each \((i,j)\), such as \((3_{a_{ij}}\,\,1_i\,\,2_j\,\,\infty_{k-3}; 2_j\,\,3_{a_{ij}+1})\), if \(a_{ij} = k+2\), \(k = 4\). Thus we may include these \(4\) copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_1\).
\(\bullet\) For all \((i,j)\in \{(5,2),(6,1),(7,8),(8,7)\}\), we have \(a_{ij} = 6\). It is possible to obtain a \(\mathcal{Y}_5\) tree corresponding to each \((i,j)\), such as \((2_{j+2}\,\,1_i\,\,2_j\,\,\infty_1; 2_j\,\,3_{a_{ij}+1})\), if \(a_{ij} = k+2\), \(k=4\). Thus we may include these \(4\) copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_1\).
\(\bullet\) For all \((i,j)\in \{(1,7),(2,6),(3,5),(4,4),(5,3),(6,2),(7,1),(8,8)\}\), we have \(a_{ij} = 7\). It is possible to obtain a \(\mathcal{Y}_5\) tree corresponding to each \((i,j)\), such as \((3_{a_{ij}}\,\,1_i\,\,2_j\,\,\infty_{k-3}; 2_j\,\,3_{k+3})\), if \(a_{ij} = k+2\), \(k=5\). Thus we may include these \(8\) copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_1\).
\(\bullet\) For all \((i,j)\in \{(1,8),(2,7),(3,6),(4,5)\}\), we have \(a_{ij} = 8\). It is possible to obtain a \(\mathcal{Y}_5\) tree corresponding to each \((i,j)\), such as \((1_i\,\,2_j\,\,3_{(a_{ij}-2)}\,\,2_i; 3_{(a_{ij}-2)}\,\,1_{i+4})\), if \(a_{ij} = k+2\), \(k=6\). Thus we may include these \(4\) copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_1\).
All together leads a \(\mathcal{Y}_5\) tree decomposition for \(K_{8,\,8,\,10}\). As a consequence of it, a gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{8,\,8,\,10})\) may derived through the use of Lemma 2.3.
(2) A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{8,\,8,\,11})\) can be derived as follows:
Let \(V(K_{8,\,8,\,11})\) \(=\) \(\{(\bigcup\limits_{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 \(\mathcal{S}_2\) of \(\mathcal{Y}_5\) tree decomposition for \(K_{8,\,8,\,11}\) as follows:
\(\bullet\) As discussed in Remark 2.1, if \(a_{ij} = a_{(i+h)(j+k)}=5\) and \(a_{i(j+k)} = a_{(i+h)j}=1\), we get the following \(\mathcal{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 \(\mathcal{Y}\) tree cells yield \(12\) copies of \(\mathcal{Y}_5\) trees.
\(\bullet\) For all \((i,j)\in \{(1,2),(2,1),(3,8),(4,7),(5,6),(6,5),(7,4),(8,3)\), we have \(a_{ij} = 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_{ij} = 3\). It is possible to obtain a \(\mathcal{Y}_5\) tree corresponding to each \((i,j)\), such as \((3_{a_{ij}}\,\,2_j\,\,1_i\,\,\infty_k; 1_i\,\,3_{k+2})\), if \(a_{ij} = k+1\), \(k=1,2\). Thus we may include these \(16\) copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_2\).
\(\bullet\) For all \((i,j)\in \{(1,4),(2,3),(3,2),(4,1),(5,8),(6,7),(7,6),(8,5)\}\), we have \(a_{ij} = 4\). It is possible to obtain a \(\mathcal{Y}_5\) tree corresponding to each \((i,j)\), such as \((3_{a_{ij}}\,\,2_j\,\,1_i\,\,\infty_k; 1_i\,\,3_{k-1})\), if \(a_{ij} = k+1\), \(k=3\). Thus we may include these \(8\) copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_2\).
\(\bullet\) For all \((i,j)\in \{(1,6),(2,5),(3,4),(4,3),(5,2),(6,1),(7,8),(8,7)\}\), we have \(a_{ij} = 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_{ij} = 7\). It is possible to obtain a \(\mathcal{Y}_5\) tree corresponding to each \((i,j)\), such as \((3_{a_{ij}}\,\,1_i\,\,2_j\,\,\infty_k; 2_j\,\,3_{(a_{ij}+1)})\), if \(a_{ij} = k+5\), \(k=1,2\). Thus we may include these \(16\) copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_2\).
\(\bullet\) For all \((i,j)\in \{(1,8),(2,7),(3,6),(4,5),(5,4),(6,3),(7,2),(8,1)\}\), we have \(a_{ij} = 8\). It is possible to obtain a \(\mathcal{Y}_5\) tree corresponding to each \((i,j)\), such as \((3_{a_{ij}}\,\,1_i\,\,2_j\,\,\infty_k; 2_j\,\,3_{(a_{ij}-2)})\), if \(a_{ij} = k+5\), \(k=3\). Thus we may include these \(8\) copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_2\).
All together leads a \(\mathcal{Y}_5\) tree decomposition for \(K_{8,\,8,\,11}\). As a consequence of it, a gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{8,\,8,\,11})\) may derived through use of Lemma 2.3.
(3) A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{8,\,8,\,12})\) can be derived as follows:
Let \(V(K_{8,\,8,\,12})\) \(=\) \(\{(\bigcup\limits_{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 \(\mathcal{S}_3\) for \(\mathcal{Y}_5\) tree decomposition of \(K_{8,\,8,\,12}\) as follows:
\(\bullet\) For all \((i,j)\in \{(1,1),(2,8),(3,7),(4,6),(5,5),(6,4),(7,3),(8,2)\}\), we have \(a_{ij} = 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_{ij} = 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_{ij} = 3\). It is possible to obtain a \(\mathcal{Y}_5\) tree corresponding to each \((i,j)\), such as \((3_{a_{ij}}\,\,2_j\,\,1_i\,\,\infty_k; 1_i\,\,3_{k+1})\), if \(a_{ij} = k\), \(k=1,2,3\). Thus we may include these \(24\) copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_3\).
\(\bullet\) For all \((i,j)\in \{(1,4),(2,3),(3,2),(4,1),(5,8),(6,7),(7,6),(8,5)\}\), we have \(a_{ij} = 4\). It is possible to obtain a \(\mathcal{Y}_5\) tree corresponding to each \((i,j)\), such as \((3_{a_{ij}}\,\,2_j\,\,1_i\,\,\infty_k; 1_i\,\,3_{k-3})\), if \(a_{ij} = k\), \(k=4\). Thus we may include these \(8\) copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_3\).
\(\bullet\) For all \((i,j)\in \{(1,5),(2,4),(3,3),(4,2),(5,1),(6,8),(7,7),(8,6)\}\), we have \(a_{ij} = 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_{ij} = 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_{ij} = 7\). It is possible to obtain a \(\mathcal{Y}_5\) tree corresponding to each \((i,j)\), such as \((3_{a_{ij}}\,\,1_i\,\,2_j\,\,\infty_k; 2_j\,\,3_{(a_{ij}+1)})\), if \(a_{ij} = k+4\), \(k=1,2,3\). Thus we may include these \(24\) copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_3\).
\(\bullet\) For all \((i,j)\in \{(1,8),(2,7),(3,6),(4,5),(5,4),(6,3),(7,2),(8,1),\}\), we have \(a_{ij} = 8\). It is possible to obtain a \(\mathcal{Y}_5\) tree corresponding to each \((i,j)\), such as \((3_{a_{ij}}\,\,1_i\,\,2_j\,\,\infty_k; 2_j\,\,3_{(k+1)})\), if \(a_{ij} = k+4\), \(k=4\). Thus we may include these \(8\) copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_3\).
All together leads a \(\mathcal{Y}_5\) tree decomposition for \(K_{8,\,8,\,12}\). As a consequence of it, a gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{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 \(\mathcal{Y}_5\) tree decomposition exists for \(\mathcal{E}_2(G)\), \(G\) \(\in\) \(\mathcal{G} = \{K_{8,\,8,\,10}, K_{8,\,8,\,11}, K_{8,\,8,\,12}\}\). ◻
Proof. (1) A gregarious \(\mathcal{Y}_5\) tree decomposition for
\(\mathcal{E}_2(K_{12,\,12,\,7})\) can
be derived as follows:
Let \(V(K_{12,\,12,\,7})\) \(=\) \(\{(\bigcup\limits_{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 \(\mathcal{S}_1\) of \(\mathcal{Y}_5\) tree decomposition for
\(K_{12,\,12,\,7}\) as follows:
| 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 | \(\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\) |
\(\bullet\) Consider the set of \(\mathcal{Y}\) tree cells \(\{a_{ij},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 \(\mathcal{Y}\) tree cell corresponding to each \((i,j)\). All together gives \(6\) copies of \(\mathcal{Y}\) tree cells. As discussed in Remark 2.1, these \(\mathcal{Y}\) tree cells will provide \(18\) copies of \(\mathcal{Y}_5\) trees.
\(\bullet\) 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_{ij} = 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_{ij} = 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_{ij} = 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_{ij} = 5\). It is possible to obtain a \(\mathcal{Y}_5\) tree corresponding to each \((i,j)\), such as \((3_{a_{ij}}\,\,2_j\,\,1_i\,\,2_{k+7-i}; 1_i\,\,3_{k+1})\), if \(a_{ij} = k\), \(k=2,3,4,5\). Thus we may include these \(48\) copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_1\).
\(\bullet\) 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_{ij} = 6\). It is possible to obtain a \(\mathcal{Y}_5\) tree corresponding to each \((i,j)\), such as \((3_{a_{ij}}\,\,2_j\,\,1_i\,\,2_{k+7-i};\\ 1_i\,\,3_{k-4})\), if \(a_{ij} = k\), \(k=6\). Thus we may include these \(12\) copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_1\). All together leads a \(\mathcal{Y}_5\) tree decomposition for \(K_{12,\,12,\,7}\). As a consequence of it, a gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{12,\,12,\,7})\) may derived through use of Lemma 2.3.
(2) A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{12,\,12,\,10})\) can be derived as follows:
Let \(V(K_{12,\,12,\,10})\) \(=\) \(\{(\bigcup\limits_{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 \(\mathcal{S}_2\) of \(\mathcal{Y}_5\) tree decomposition for \(K_{12,\,12,\,10}\) as follows:
| 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\) |
\(\bullet\) Consider the set of \(\mathcal{Y}\) tree cells \(\{a_{ij},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 \(\mathcal{Y}\) tree cell for each \((i,j)\). All together gives \(24\) copies of \(\mathcal{Y}\) tree cells. As discussed in Remark 2.1, the \(\mathcal{Y}\) tree cells will provide \(72\) copies of \(\mathcal{Y}_5\) trees.
\(\bullet\) 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_{ij} = 5\). It is possible to obtain a \(\mathcal{Y}_5\) tree corresponding to each \((i,j)\), such as \((3_{a_{ij}}\,\,2_j\,\,1_i\,\,2_{k+7-i};\\ 1_i\,\,3_{k+1})\), if \(a_{ij} = k\), \(k=5\). Thus we may include these \(12\) copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_2\).
\(\bullet\) 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_{ij} = 6\). It is possible to obtain a \(\mathcal{Y}_5\) tree for each \((i,j)\), such as \((3_{a_{ij}}\,\,2_j\,\,1_i\,\,2_{k+7-i}; 1_i\,\,3_{k-1})\), if \(a_{ij} = k\), \(k=6\). Thus we may include these \(12\) copies of \(\mathcal{Y}_5\) trees in \(\mathcal{S}_2\).
All together leads a \(\mathcal{Y}_5\) tree decomposition for \(K_{12,\,12,\,10}\). As a consequence of it, a gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{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 \(\mathcal{Y}_5\) tree decomposition exists for \(\mathcal{E}_2(G)\), \(G\) \(\in\) \(\mathcal{G} = \{K_{12,\,12,\,7}, K_{12,\,12,\,10}\}\). ◻
Proof. (1) Let us consider \(V(K_{10} \setminus K_7) = \{1,2,3,\ldots,10\}\) and \[\mathcal{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 \(\mathcal{S}_1\) provides a \(\mathcal{Y}_5\) tree decomposition of \(K_{10} \setminus K_7\).
(2) By taking \(V(K_{11} \setminus K_6) = \{1,2,3,\ldots,11\}\), the set \(\mathcal{S}_2\) given bellow derives a \(\mathcal{Y}_5\) tree decomposition of \(K_{11} \setminus K_6\). \[\begin{aligned} \mathcal{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), \\ \notag &(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} \setminus K_5) = \{1,2,3,\ldots,12\}\), a \(\mathcal{Y}_5\) tree decomposition for \(K_{12} \setminus K_5\) is contained with in the set \(\mathcal{S}_3\) mentioned bellow. \[\begin{aligned} \mathcal{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), \\ \notag &(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), \\ \notag &(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} \setminus K_5) = \{1,2,3,\ldots,13\}\), the collection \(\mathcal{S}_4\) gives a \(\mathcal{Y}_5\) tree decomposition of \(K_{13} \setminus K_5\). \[\begin{aligned} \mathcal{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), \\ \notag &(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), \\ \notag &(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),\\ \notag &(12\,\,2\,\,10\,\,7; 10\,\,8),(4\,\,1\,\,2\,\,6; 2\,\,8)\}. \end{aligned}\]
(5) By considering \(V(K_{14} \setminus K_6) = \{1,2,3,\ldots,14\}\), the set \(\mathcal{S}_5\) must be a \(\mathcal{Y}_5\) tree decomposition of \(K_{14} \setminus K_6\). \[\begin{aligned} \mathcal{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), \\ \notag &(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), \\ \notag &(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),\\ \notag &(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} \setminus K_7) = \{1,2,3,\ldots,15\}\). The set \(\mathcal{S}_6\) leads a \(\mathcal{Y}_5\) tree decomposition of \(K_{15} \setminus K_7\). \[\begin{aligned} \mathcal{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),\\ \notag &(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),\\ \notag &(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),\\\notag &(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),\\ \notag &(7\,\,15\,\,1\,\,8; 1\,\,5),(14\,\,4\,\,2\,\,3; 2\,\,11)\}. \end{aligned}\]
(7) By considering \(V(K_{16} \setminus K_8) = \{1,2,3,\ldots,16\}\), the set \(\mathcal{S}_7\) provides a \(\mathcal{Y}_5\) tree decomposition of \(K_{16} \setminus K_8\). \[\begin{aligned} \mathcal{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),\\ \notag &(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),\\ \notag &(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),\\ \notag &(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),\\ \notag &(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} \setminus K_{14}) = \{1,2,3,\ldots,19\}\). A \(\mathcal{Y}_5\) tree decomposition of \(K_{19} \setminus K_{14}\) belongs to \(\mathcal{S}_8\). \[\begin{aligned} \mathcal{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),\\ \notag &(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),\\ \notag &(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),\\ \notag &(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} \setminus K_{13}) = \{1,2,3,\ldots,20\}\). A \(\mathcal{Y}_5\) tree decomposition of \(K_{20} \setminus K_{13}\) is contained in \(\mathcal{S}_9\). \[\begin{aligned} \mathcal{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),\\ \notag &(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),\\ \notag &(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),\\ \notag &(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),\\ \notag &(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),\\ \notag &(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} \setminus K_{20}) = \{1,2,3,\ldots,29\}\). A \(\mathcal{Y}_5\) tree decomposition of \(K_{29} \setminus K_{20}\) has been constructed as follows: \[\begin{aligned} \mathcal{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),\\ \notag &(5\,\,13\,\,9\,\,16; 9\,\,21),(6\,\,14\,\,1\,\,20; 1\,\,22),(5\,\,27\,\,2\,\,21; 2\,\,23),(6\,\,27\,\,3\,\,22; 3\,\,24),\\ \notag &(7\,\,3\,\,4\,\,23; 4\,\,25),(8\,\,29\,\,5\,\,24; 5\,\,26),(10\,\,1\,\,6\,\,25; 6\,\,28),(11\,\,2\,\,24\,\,4; 24\,\,9),\\ \notag &(12\,\,7\,\,14\,\,5; 14\,\,4),(13\,\,4\,\,15\,\,3; 15\,\,2),(10\,\,5\,\,16\,\,6; 16\,\,3),(11\,\,6\,\,7\,\,8; 7\,\,26),\\ \notag &(12\,\,3\,\,10\,\,9; 10\,\,8),(13\,\,8\,\,11\,\,9; 11\,\,4),(8\,\,27\,\,7\,\,18; 7\,\,29),(9\,\,28\,\,8\,\,19; 8\,\,18),\\ \notag &(29\,\,1\,\,12\,\,9; 12\,\,2),(6\,\,2\,\,13\,\,3; 13\,\,1),(22\,\,7\,\,4\,\,29; 4\,\,26),(7\,\,28\,\,3\,\,23; 3\,\,25),\\ \notag &(17\,\,9\,\,7\,\,23; 7\,\,20),(25\,\,1\,\,8\,\,24; 8\,\,21),(26\,\,2\,\,9\,\,25; 9\,\,22),(15\,\,5\,\,1\,\,26; 1\,\,23),\\ \notag &(26\,\,6\,\,5\,\,25; 5\,\,4),(3\,\,8\,\,9\,\,14; 9\,\,29),(14\,\,2\,\,7\,\,10; 7\,\,17),(8\,\,4\,\,9\,\,20; 9\,\,19),\\ \notag &(22\,\,2\,\,1\,\,11; 1\,\,21),(3\,\,6\,\,15\,\,1; 15\,\,7),(28\,\,4\,\,16\,\,2; 16\,\,8),(5\,\,8\,\,17\,\,3; 17\,\,6),\\ \notag &(6\,\,9\,\,18\,\,4; 18\,\,1),(7\,\,1\,\,19\,\,5; 19\,\,2),(8\,\,2\,\,20\,\,6; 20\,\,3),(9\,\,3\,\,21\,\,7; 21\,\,4),\\ \notag &(10\,\,4\,\,22\,\,8; 22\,\,5),(11\,\,5\,\,23\,\,9; 23\,\,6),(12\,\,6\,\,24\,\,1; 24\,\,7),(13\,\,7\,\,25\,\,2; 25\,\,8),\\ \notag &(14\,\,8\,\,26\,\,3; 26\,\,9),(15\,\,9\,\,27\,\,4; 27\,\,1),(16\,\,1\,\,28\,\,5; 28\,\,2),(17\,\,2\,\,29\,\,6; 29\,\,3),\\ \notag &(18\,\,3\,\,1\,\,17; 1\,\,4),(19\,\,4\,\,2\,\,18; 2\,\,5),(20\,\,5\,\,7\,\,19; 7\,\,16),(21\,\,6\,\,4\,\,20; 4\,\,17),\\ \notag &(2\,\,3\,\,5\,\,21; 5\,\,18),(23\,\,8\,\,6\,\,22; 6\,\,19)\}. \end{aligned}\]
(11) Let \(V(K_{35} \setminus K_{30}) = \{1,2,3,\ldots,35\}\). A \(\mathcal{Y}_5\) tree decomposition of \(K_{35} \setminus K_{30}\) is shown bellow: \[\begin{aligned} \mathcal{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),\\ \notag &(2\,\,22\,\,4\,\,13; 4\,\,6),(3\,\,23\,\,5\,\,14; 5\,\,7),(4\,\,24\,\,1\,\,15; 1\,\,8),(4\,\,25\,\,2\,\,16; 2\,\,9),\\ \notag &(1\,\,26\,\,3\,\,19; 3\,\,10),(2\,\,27\,\,4\,\,18; 4\,\,11),(3\,\,28\,\,5\,\,25; 5\,\,12),(4\,\,29\,\,1\,\,20; 1\,\,13),\\ \notag &(5\,\,30\,\,2\,\,13; 2\,\,14),(1\,\,31\,\,3\,\,14; 3\,\,15),(2\,\,32\,\,4\,\,15; 4\,\,16),(3\,\,33\,\,5\,\,16; 5\,\,17),\\ \notag &(4\,\,34\,\,1\,\,17; 1\,\,18),(5\,\,35\,\,2\,\,18; 2\,\,19),(3\,\,17\,\,2\,\,23; 2\,\,7),(5\,\,26\,\,4\,\,21; 4\,\,23),\\ \notag &(1\,\,27\,\,5\,\,22; 5\,\,24),(2\,\,28\,\,1\,\,23; 1\,\,25),(3\,\,29\,\,2\,\,24; 2\,\,26),(4\,\,30\,\,3\,\,25; 3\,\,27),\\ \notag &(5\,\,31\,\,4\,\,28; 4\,\,20),(1\,\,32\,\,5\,\,29; 5\,\,19),(2\,\,33\,\,1\,\,30; 1\,\,14),(3\,\,34\,\,2\,\,31; 2\,\,15),\\ \notag &(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),\\ \notag &(10\,\,5\,\,8\,\,4; 8\,\,2),(11\,\,1\,\,9\,\,5; 9\,\,3),(12\,\,2\,\,10\,\,1; 10\,\,4),(13\,\,3\,\,11\,\,2; 11\,\,5),\\ \notag &(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 \(\mathcal{Y}_5\) tree decomposition for each \(G\) \(\in\) \(\mathcal{G}\) \(=\) \(\{K_{10}\setminus K_7, K_{11}\setminus K_6, K_{12}\setminus K_5, K_{13}\setminus K_5, K_{14}\setminus K_6, K_{15}\setminus K_7, K_{16}\setminus K_8, K_{19}\setminus K_{14}, K_{20}\setminus K_{13}, K_{29}\setminus K_{20}, K_{35}\setminus K_{30}\}\). By applying Lemma 2.3, we can produce a gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(G)\), \(G\) \(\in\) \(\mathcal{G}\) \(=\) \(\{K_{10}\setminus K_7, K_{11}\setminus K_6, K_{12}\setminus K_5, K_{13}\setminus K_5, K_{14}\setminus K_6, K_{15}\setminus K_7, K_{16}\setminus K_8, K_{19}\setminus K_{14}, K_{20}\setminus K_{13}, K_{29}\setminus K_{20}, K_{35}\setminus K_{30}\}\). ◻
Proof. A gregarious \(\mathcal{Y}_5\) tree decomposition of \(\mathcal{E}_2(K_i)\), \(i\in \{5,6,7\}\) have been discribed as follows: \[\begin{aligned} \mathcal{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\\ \notag &(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\\ \notag &(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\\ \notag &(2_2\,\,5_1\,\,4_1\,\,3_1; 4_1\,\,1_1)\}. \end{aligned}\] \[\begin{aligned} \mathcal{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\\ \notag &(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\\ \notag &(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\\ \notag &(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} \mathcal{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\\ \notag &(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\\ \notag &(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\\ \notag &(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\\ \notag &(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\\ \notag &(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}\] ◻
Proof. A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{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}\setminus K_7\). We then write \(\mathcal{E}_2(K_{10})\) \(=\) \(\mathcal{E}_2(K_{7})\oplus \mathcal{E}_2(K_{10}\setminus K_7)\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{10}\setminus K_7)\) and \(\mathcal{E}_2(K_{7})\) have been respectively derived in Lemmas 2.9 and 2.10. A gregarious \(\mathcal{Y}_5\) tree decomposition has been found for \(\mathcal{E}_2(K_{10})\).
Let \(K_{11}\) \(=\) \(K_6\) \(\oplus\) \(K_{11}\setminus K_6\). We then write \(\mathcal{E}_2(K_{11})\) \(=\) \(\mathcal{E}_2(K_6)\) \(\oplus\) \(\mathcal{E}_2(K_{11}\setminus K_6)\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{11}\setminus K_6)\) and \(\mathcal{E}_2(K_6)\) have been respectively derived in Lemmas 2.9 and 2.10. Hence, we concluded that, \(\mathcal{E}_2(K_{11})\) has a gregarious \(\mathcal{Y}_5\) tree decomposition.
Let \(K_{12}\) \(=\) \(K_5\) \(\oplus\) \(K_{12}\setminus K_5\). We then write \(\mathcal{E}_2(K_{12})\) \(=\) \(\mathcal{E}_2(K_5)\) \(\oplus\) \(\mathcal{E}_2(K_{12}\setminus K_5)\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{12}\setminus K_5)\) and \(\mathcal{E}_2(K_5)\) have been respectively derived in Lemmas 2.9 and 2.10. Our conclusion was that, \(\mathcal{E}_2(K_{12})\) has a gregarious \(\mathcal{Y}_5\) tree decomposition.
Let \(K_{13}\) \(=\) \(K_5\) \(\oplus\) \(K_{13}\setminus K_5\). We then write \(\mathcal{E}_2(K_{13})\) \(=\) \(\mathcal{E}_2(K_5)\) \(\oplus\) \(\mathcal{E}_2(K_{13}\setminus K_5)\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{13}\setminus K_5)\) and \(\mathcal{E}_2(K_5)\) have been respectively derived in Lemmas 2.9 and 2.10. A gregarious \(\mathcal{Y}_5\) tree decomposition is obtained for \(\mathcal{E}_2(K_{13})\).
Let \(K_{14}\) \(=\) \(K_6\) \(\oplus\) \(K_{14}\setminus K_6\). We then write \(\mathcal{E}_2(K_{14})\) \(=\) \(\mathcal{E}_2(K_6)\) \(\oplus\) \(\mathcal{E}_2(K_{14}\setminus K_6)\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{14}\setminus K_5)\) and \(\mathcal{E}_2(K_6)\) have been respectively derived in Lemmas 2.9 and 2.10. Consequently, \(\mathcal{E}_2(K_{14})\) is decomposed into a gregarious \(\mathcal{Y}_5\) tree.
Let \(K_{15}\) \(=\) \(K_7\) \(\oplus\) \(K_{15}\setminus K_7\). We then write \(\mathcal{E}_2(K_{15})\) \(=\) \(\mathcal{E}_2(K_7)\) \(\oplus\) \(\mathcal{E}_2(K_{15}\setminus K_7)\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{15}\setminus K_7)\) and \(\mathcal{E}_2(K_7)\) have been respectively derived in Lemmas 2.9 and 2.10. A gregarious \(\mathcal{Y}_5\) tree decomposition has been found for \(\mathcal{E}_2(K_{15})\).
Let \(K_{18}\) \(=\) 3\(K_6\) \(\oplus\) \(K_{6,\,6,\,6}\). We then write \(\mathcal{E}_2(K_{18})\) \(=\) 3 \(\mathcal{E}_2(K_6)\) \(\oplus\) \(\mathcal{E}_2(K_{6,\,6,\,6})\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{6,\,6,\,6})\) and \(\mathcal{E}_2(K_6)\) have been respectively derived in Lemmas 2.5 and 2.10. A gregarious \(\mathcal{Y}_5\) tree decomposition has been found for \(\mathcal{E}_2(K_{18})\).
For \(\mathcal{E}_2(K_{i})\), \(i \in \{10,11,12,13,14,15,18\}\), a gregarious \(\mathcal{Y}_5\) tree decomposition was obtained from (1) – (7). ◻
Proof. A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{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}\setminus K_{14}\). We then write \(\mathcal{E}_2(K_{19})\) \(=\) \(\mathcal{E}_2(K_{14})\) \(\oplus\) \(\mathcal{E}_2(K_{19}\setminus K_{14})\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{19}\setminus K_{14})\) and \(\mathcal{E}_2(K_{14})\) have been respectively derived in Lemmas 2.9 and 2.11. A gregarious \(\mathcal{Y}_5\) tree decomposition has been found for \(\mathcal{E}_2(K_{19})\).
Let \(K_{20}\) \(=\) \(K_{13}\) \(\oplus\) \(K_{20}\setminus K_{13}\). We then write \(\mathcal{E}_2(K_{20})\) \(=\) \(\mathcal{E}_2(K_{13})\) \(\oplus\) \(\mathcal{E}_2(K_{20}\setminus K_{13})\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{20}\setminus K_{13})\) and \(\mathcal{E}_2(K_{13})\) have been respectively derived in Lemmas 2.9 and 2.11. Hence, we concluded that, \(\mathcal{E}_2(K_{20})\) has a gregarious \(\mathcal{Y}_5\) tree decomposition.
Let \(K_{29}\) \(=\) \(K_{20}\) \(\oplus\) \(K_{29}\setminus K_{20}\). We then write \(\mathcal{E}_2(K_{29})\) \(=\) \(\mathcal{E}_2(K_{20})\) \(\oplus\) \(\mathcal{E}_2(K_{29}\setminus K_{20})\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{29}\setminus K_{20})\) and \(\mathcal{E}_2(K_{20})\) have been respectively derived in Lemma 2.9 and in the above Case 2. Our conclusion was that, \(\mathcal{E}_2(K_{29})\) has a gregarious \(\mathcal{Y}_5\) tree decomposition.
Let \(K_{30}\) \(=\) 3\(K_{10}\) \(\oplus\) \(K_{10,\,10,\,10}\). We then write \(\mathcal{E}_2(K_{30})\) \(=\) 3 \(\mathcal{E}_2(K_{10})\) \(\oplus\) \(\mathcal{E}_2(K_{10,\,10,\,10})\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{10})\) and \(\mathcal{E}_2(K_{10,\,10,\,10})\) have been respectively derived in Lemmas 2.11 and 2.5. A gregarious \(\mathcal{Y}_5\) tree decomposition is obtained for \(\mathcal{E}_2(K_{30})\).
Let \(K_{31}\) \(=\) 2\(K_{12}\) \(\oplus\) \(K_7\) \(\oplus\) \(K_{12,\,12,\,7}\). We then write \(\mathcal{E}_2(K_{31})\) \(=\) 2 \(\mathcal{E}_2(K_{12})\) \(\oplus\) \(\mathcal{E}_2(K_{7})\) \(\oplus\) \(\mathcal{E}_2(K_{12,\,12,\,7})\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{7})\), \(\mathcal{E}_2(K_{12})\) and \(\mathcal{E}_2(K_{12,\,12,\,7})\) have been respectively derived in Lemmas 2.10, 2.11 and 2.8. Consequently, \(\mathcal{E}_2(K_{31})\) is decomposed into a gregarious \(\mathcal{Y}_5\) tree.
Let \(K_{34}\) \(=\) 2\(K_{12}\) \(\oplus\) \(K_{10}\) \(\oplus\) \(K_{12,\,12,\,10}\). We then write \(\mathcal{E}_2(K_{34})\) \(=\) 2 \(\mathcal{E}_2(K_{12})\) \(\oplus\) \(\mathcal{E}_2(K_{10})\) \(\oplus\) \(\mathcal{E}_2(K_{12,\,12,\,10})\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{10})\), \(\mathcal{E}_2(K_{12})\) and \(\mathcal{E}_2(K_{12,\,12,\,10})\) have been derived in Lemmas 2.11 and 2.8. A gregarious \(\mathcal{Y}_5\) tree decomposition has been found for \(\mathcal{E}_2(K_{34})\).
Let \(K_{35}\) \(=\) \(K_{30}\) \(\oplus\) \(K_{35}\setminus K_{30}\). We then write \(\mathcal{E}_2(K_{35})\) \(=\) \(\mathcal{E}_2(K_{30})\) \(\oplus\) \(\mathcal{E}_2(K_{35}\setminus K_{30})\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{35}\setminus K_{30})\) and \(\mathcal{E}_2(K_{30})\) have been respectively derived in Lemma 2.9 and in the above Case 4. A gregarious \(\mathcal{Y}_5\) tree decomposition has been found for \(\mathcal{E}_2(K_{35})\).
Let \(K_{36}\) \(=\) 3\(K_{12}\) \(\oplus\) \(K_{12,\,12,\,12}\). Then, we write \(\mathcal{E}_2(K_{36})\) \(=\) 3 \(\mathcal{E}_2(K_{12})\) \(\oplus\) \(\mathcal{E}_2(K_{12,\,12,\,12})\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{12})\) and \(\mathcal{E}_2(K_{12,\,12,\,12})\) have been respectively derived in Lemmas 2.11 and 2.5. A gregarious \(\mathcal{Y}_5\) tree decomposition has been found for \(\mathcal{E}_2(K_{36})\).
For \(\mathcal{E}_2(K_{i})\), \(i \in \{19,20,29,30,31,34,35,36\}\), a gregarious \(\mathcal{Y}_5\) tree decomposition was obtained from (1) – (8). ◻
Proof. Consider the graph \(K_m(2)\) \(\simeq\) \(\mathcal{E}_2(K_m)\) and let \(m = 8s+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 \pmod 6\), (ii) \(s \equiv 4 \pmod 6\), (iii) \(s \equiv 1,5 \pmod 6\) and (iv) \(s \equiv 3 \pmod 6\).
Case i: For \(s \equiv 0,2 \pmod 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- 2s}{6}\) copies of \(K_{8,\,8,\,8}\). Therefore, \(\mathcal{E}_2(K_m)\) \(=\) \(\mathcal{E}_2 \big(K_a \oplus s\,K_8 \oplus \frac{s}{2}\, K_{8,\,8,\,a} \oplus \frac{s^2- 2s}{6}\,K_{8,\,8,\,8}\big)\) \(=\) \(\mathcal{E}_2(K_a)\) \(\oplus\) \(s\,\mathcal{E}_2(K_8)\) \(\oplus\) \(\frac{s}{2}\,\mathcal{E}_2(K_{8,\,8,\,a})\) \(\oplus\) \(\frac{s^2-2s}{6}\, \mathcal{E}_2(K_{8,\,8,\,8})\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_a)\) and \(\mathcal{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 \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{8,\,8,\,8})\) . Also, the Lemmas 2.6 and 2.7 have been used to obtain a gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2(K_{8,\,8,\,a})\) . Consequently, it proves that a gregarious \(\mathcal{Y}_5\) tree decomposition exists for \(\mathcal{E}_2(K_m)\).
Case ii: For \(s \equiv 4 \pmod 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- 2s-8}{6}\) copies of \(K_{8,\,8,\,8}\) and 4 copies of \(K_{16} \setminus K_8\). Therefore, \(\mathcal{E}_2(K_m)\) \(=\) \(\mathcal{E}_2 \big(K_a \oplus (s-4)\,K_8 \oplus \frac{s}{2}\, K_{8,\,8,\,a} \oplus \frac{s^2- 2s-8}{6}\,K_{8,\,8,\,8} \oplus 4\,(K_{16} \setminus K_8)\big)\) \(=\) \(\mathcal{E}_2(K_a)\) \(\oplus\) \((s-4)\,\mathcal{E}_2(K_8)\) \(\oplus\) \(\frac{s}{2}\, \mathcal{E}_2(K_{8,\,8,\,a})\) \(\oplus\) \(\frac{s^2-2s-8}{6}\, \mathcal{E}_2(K_{8,\,8,\,8})\) \(\oplus\) \(4 \,\mathcal{E}_2(K_{16}\setminus K_8)\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2 (K_{8,\,8,\,8})\) have been obtained from the Lemma 2.5. Further more, a gregarious \(\mathcal{Y}_5\) tree decomposition have been obtained for \(\mathcal{E}_2(K_{8,\,8,\,a})\) from the Lemmas 2.6 and 2.7 Also, a gregarious \(\mathcal{Y}_5\) tree decomposition have been obtained for \(\mathcal{E}_2(K_{16}\setminus K_8)\) from the Lemma 2.9. In addition with, a gregarious \(\mathcal{Y}_5\) tree decomposition have been obtained for \(\mathcal{E}_2(K_a)\) and \(\mathcal{E}_2(K_8)\) from the Lemmas 2.10, 2.11 and 2.4. Consequently, it proves that a gregarious \(\mathcal{Y}_5\) tree decomposition exists for \(\mathcal{E}_2(K_m)\).
Case iii: For \(s \equiv 1,5 \pmod 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- 3s+2}{6}\) copies of \(K_{8,\,8,\,8}\). Therefore, \(\mathcal{E}_2(K_m)\) \(=\) \(\mathcal{E}_2 \big(K_{a+8} \oplus \frac{s-1}{2}\,K_{16} \oplus \frac{s-1}{2}\,K_{8,\,8,\,a} \oplus \frac{s^2- 3s+2}{6}\,K_{8,\,8,\,8}\big)\) \(=\) \(\mathcal{E}_2(K_{a+8})\) \(\oplus\) \(\frac{s-1}{2}\,\mathcal{E}_2(K_{16})\) \(\oplus\) \(\frac{s-1}{2}\,\mathcal{E}_2(K_{8,\,8,\,a})\) \(\oplus\) \(\frac{s^2-3s+2}{6}\,\mathcal{E}_2(K_{8,\,8,\,8})\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2 (K_{8,\,8,\,8})\) have been obtained from the Lemma 2.5. Further more, a gregarious \(\mathcal{Y}_5\) tree decomposition have been obtained for \(\mathcal{E}_2(K_{8,\,8,\,a})\) from the Lemmas 2.6 and 2.7. Also, a gregarious \(\mathcal{Y}_5\) tree decomposition have been obtained for \(\mathcal{E}_2(K_{a+8})\) from the Lemmas 2.11 and 2.12. In addition with, a gregarious \(\mathcal{Y}_5\) tree decomposition have been obtained for \(\mathcal{E}_2(K_{16})\) from the Lemma 2.4. Consequently, it proves that a gregarious \(\mathcal{Y}_5\) tree decomposition exists for \(\mathcal{E}_2(K_m)\).
Case iv: For \(s \equiv 3 \pmod 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-3s}{6}\) copies of \(K_{8,\,8,\,8}\). Therefore, \(\mathcal{E}_2(K_m)\) \(=\) \(\mathcal{E}_2 \big(K_{a+24} \oplus \frac{s-3}{2}\,K_{16} \oplus \frac{s-3}{2}\,K_{8,\,8,\,a} \oplus \frac{s^2-3s}{6}\,K_{8,\,8,\,8}\big)\) \(=\) \(\mathcal{E}_2(K_{a+24})\) \(\oplus\) \(\frac{s-3}{2}\, \mathcal{E}_2(K_{16})\) \(\oplus\) \(\frac{s-3}{2}\,\mathcal{E}_2(K_{8,\,8,\,a})\) \(\oplus\) \(\frac{s^2-3s}{6}\,\mathcal{E}_2(K_{8,\,8,\,8})\). A gregarious \(\mathcal{Y}_5\) tree decomposition for \(\mathcal{E}_2 (K_{8,\,8,\,8})\) have been obtained from the Lemma 2.5. Further more, a gregarious \(\mathcal{Y}_5\) tree decomposition have been obtained for \(\mathcal{E}_2(K_{8,\,8,\,a})\) from the Lemmas 2.6 and 2.7. Also, a gregarious \(\mathcal{Y}_5\) tree decomposition have been obtained for \(\mathcal{E}_2(K_{a+24})\) from the Lemma 2.12. In addition with, a gregarious \(\mathcal{Y}_5\) tree decomposition have been obtained for \(\mathcal{E}_2(K_{16})\) from the Lemma 2.4. Consequently, it proves that a gregarious \(\mathcal{Y}_5\) tree decomposition exists for \(\mathcal{E}_2(K_m)\).
The Cases (i) – (iv) mentioned earlier will provide a gregarious \(\mathcal{Y}_5\) tree decomposition for \(K_m(2)\). ◻
Proof. Necessity: Given that \(\mid E(K_m(n))\mid\) \(=\) \(\frac{n^2m(m-1)}{2}\) and \(\mid E(\mathcal{Y}_5)\mid = 4\). To determine a gregarious \(\mathcal{Y}_5\) tree decomposition for \(K_m(n)\), the necessary condition for edge divisibility has been expressed as \(\frac{\mid E(K_m(n)\mid}{\mid E(\mathcal{Y}_5)\mid}\) \(=\) \(\frac{n^2m(m-1)}{2 \times 4}\). That is, \(8|n^2m(m-1)\). It can be written as \(n^2m(m-1) \equiv 0 \pmod 8\).
Sufficiency: The occurence of a gregarious \(\mathcal{Y}_5\) tree decomposition for \(K_m(n)\) has been described in Lemmas 2.4 and 2.14. ◻
In this document, we present a complete and detailed solution to the problem of identifying the presence of a gregarious \(\mathcal{Y}_5\) tree decomposition in \(K_m(n)\). Decomposing \(K_ m(n)\) into a \(\mathcal{Y}_k\) tree (gregarious \(\mathcal{Y}_ k\) tree) is generally a challanging task for \(k \geq 6\).
1970-2025 CP (Manitoba, Canada) unless otherwise stated.