Menu
A kite \(K\) is a graph which can be obtained by joining an edge to any vertex of \(K_3\). A kite with edge set \(\{ab,\,bc,\,ca,\,cd\}\) can be denoted as \((a,\,b,\,c;\,cd)\). If every vertex of a kite in the decomposition lies in different partite sets, then we say that a kite decomposition of a multipartite graph is a gregarious kite decomposition. In this manuscript, it is shown that there exists a decomposition of \((K_m \otimes \overline{K}_n) \times (K_r \otimes \overline{K}_s) \) into gregarious kites if and only if
\[
n^2 s^2 m(m-1)r(r-1) \equiv 0 \pmod{8},
\]
where \(\otimes\) and \(\times\) denote the wreath product and tensor product of graphs respectively. We denote a gregarious kite decomposition as \(\it GK\)-decomposition.
Many authors have been studied on kite-design and kite decomposition/ kite factorization and their special properties such as gregarious kite decomposition/ gregarious kite factorization. Bermond and Schonheim [1] proved that a kite-design of order \(n\) exists if and only if \(n\equiv 0,\, 1\pmod 8\). Wang and Chang [2,3] considered the problem of a resolvable \((K_{3}+e)\) and \((K_3 + e,\, \lambda)\)-group divisible designs of type \(g^t u^1.\) Wang [4] have proven that the necessary conditions to find a resolvable \((K_{3}+e)\)-group divisible design of type \(g^u\) are also sufficient. Fu et al. [5] have demonstrated that there exists a \(\it GK\)-decomposition of \(K_m(n)\) if and only if \(n \equiv 0,\,1 \pmod 8\) for odd \(m\) or \(n\geq 4\) for even \(m.\) Gionfriddo and Milici [6] considered the uniformly resolvable decompositions of \(K_v\) and \(K_v – I\) into paths and kites. To know more about kite designs, refer [7-11]. Further, the authors A. Tamil Elakkiya and A. Muthusamy [12] have shown that there is a \(\it GK\)-decomposition of \(K_m \times K_n\) if and only if \(mn (m-1) (n-1)\equiv 0 \pmod 8.\) Moreover, the authors A. Tamil Elakkiya and A. Muthusamy [13] considered the existence of a \(\it GK\) factorization of tensor product of complete graphs.
In this way, our main concern is to find a existence of a \(\it GK\)-decomposition of \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s)\). In this document, it is demonstrated that a \(\it GK\)-decomposition of \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s)\) holds, if and only if, \(n^2 s^2 m(m-1)r(r-1)\equiv 0 \pmod 8.\)
Definition 1. [12] A partition of a graph \(G\) into a collection of subgraphs \(G_1,\,G_2,\,\ldots,\,G_r\) such that each one of it is distinct mutually by their edges together with \(E(G)= \cup_{i=1}^{r} E(G_i)\) is called a decomposition of \(G;\) We then write \(G\) as \(G=G_1\,\oplus\,G_2\,\oplus\,\ldots \oplus\, G_r,\) where \(\oplus\) denotes edge-disjoint sum of subgraphs. For an integer \(s,\) \(s G\) denotes \(s\) copies of \(G.\)
Definition 2. [12] A kite \(K\) is a graph which can be obtained by joining an edge to any vertex of \(K_3\), for instance see Figure 1. A kite with edge set \(\{ab,\,bc,\,ca,\,cd\}\) can be denoted as \((a,\,b,\,c;\,cd)\).
If every vertex of a kite in the decomposition lies in different partite sets, then we say that a kite decomposition of a multipartite graph is a gregarious kite decomposition. Here we may consider a Gregarious Kite decomposition as a \(\it GK\)-decomposition for short.
Definition 3. [12] The tensor product \(G \times H\) and the wreath product \(G \otimes H\) of two graphs \(G\) and \(H\) are defined as follows: \(V(G \times H)\)=\(V(G \otimes H)\) = \(\{(u,\,v) \mid u \in V(G),\, v\in V(H)\}.\) \(E(G\times H)\) = \(\{(u,\,v)\,(x,\,y)\mid u\,x\in E(G)\) and \(v\,y\in E(H)\}\) and \(E(G \otimes H)\) = \(\{(u,\,v)\,(x,\,y)\mid u = x\) and \(v\,y\in E(H)\) or \(u\,x\in E(G)\}.\)
As tensor product has commutative and distributive property over an edge-disjoint sum of subgraphs, if decomposition of \(G\) = \(G_1\,\oplus\,G_2\,\oplus\,\ldots \oplus\, G_r\) holds, we then write as \(G \times H\) = \((G_1\times H)\oplus (G_2\times H)\oplus \ldots \oplus (G_r\times H).\)
Definition 4. [12] A graph \(G\) having partite sets \(V_1,\,V_2,\,\ldots, V_m\) with \(\mid V_i\mid = n,\) \(1\leq i \leq n\) and \(E(G)\) ={\(uv\) \(\mid\) \(u\in V_i\) and \(v \in V_j,\,\forall\, i \neq j\)} is called complete \(m\)-partite graph and is denoted by \(K_m(n).\) Note that \(K_m(n)\) is same as the \(K_m \otimes \overline K_n.\) where \(\overline K_n\) is the complement of a complete graph on \(n\) vertices.
In order to prove our key result, we require the following:
Theorem 1. [5] There exists a \(\it GK\)-decomposition of \(K_m(n)\) if and only if \(m\equiv 0,\,1 \pmod 8,\) for all odd \(n\) (or) \(m \geq 4,\) for even \(n.\)
Remark 1. [5] Let \(K\) is a kite. Then there exists a \(\it GK\)-decomposition of \(K\otimes \overline K_s,\) for all \(s.\)
Lemma 1. [12] For all \(n,\) \(n \neq 2\), there exists a \(\it GK\)-decomposition of \(K \times K_{n},\) where \(K\) is a kite.
Theorem 2. [12] There exists a \(\it GK\)-decomposition of \(K_m \times K_{n}\) if and only if \(mn (m-1) (n-1)\equiv 0 \pmod 8.\)
Lemma 2. A \(\it GK\)-decomposition of \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s)\) exists, if \(m \equiv 0,\,1 \pmod 8,\) \(n,\,s \equiv 1 \pmod 2\) and for all \(r,\) \(r \neq 2.\)
Proof. By Theorem 1, we have a \(\it GK\)-decomposition of \((K_m \otimes \overline K_n).\) Then \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s)\) = \((K \oplus\, K \oplus\,\ldots\,\oplus K)\times (K_r \otimes \overline K_s)\) = \(K \times (K_r \otimes \overline K_s) \oplus\, K \times (K_r \otimes \overline K_s)\oplus\, \ldots \oplus\, K\times (K_r \otimes \overline K_s).\) Now \(K\times (K_r \otimes \overline K_s) \cong (K\times K_r) \otimes \overline K_s.\) As we have a kite decomposition of \(K\times K_r\) from Lemma 1, we then write as \((K\times K_r) \otimes \overline K_s\) = \((K \oplus\, K \oplus\,\ldots\,\oplus\, K) \otimes \overline K_s\) = \((K\otimes\overline K_s) \oplus\, (K\otimes\overline K_s) \oplus\, \ldots \oplus\, (K\otimes\overline K_s).\) A \(\it GK\)-decomposition of \(K\otimes\overline K_s\) can be obtained from Remark 1. Thus all together provides a \(\it GK\)-decomposition of \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s).\) ◻
Lemma 3. A \(\it GK\)-decomposition of \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s)\) exists, if \(n \equiv 0 \pmod 2\) and for all \(m,\,r,\,s,\) \(\{m,\,r \}\neq 2.\)
Proof. Case 1: Let \(m = 3,\) \(n = 2b,\,b\geq 0\) and for all \(r,\,s,\, (r\neq 2).\) We write \((K_3 \otimes \overline K_n) \times (K_r \otimes \overline K_s) \cong [(K_3 \otimes \overline K_n) \times K_r] \otimes \overline K_s\) = \([(K_3\oplus\, K_3\oplus\, \ldots\oplus\, K_3)\times K_r] \otimes \overline K_s\) = \([(K_3\times K_r)\oplus\,(K_3\times K_r)\oplus\,\ldots \oplus\,(K_3\times K_r)] \otimes \overline K_s\) = \([(K_3\times K_r)\otimes \overline K_s]\oplus\, [(K_3\times K_r)\otimes \overline K_s]\oplus\, \ldots \oplus\, [(K_3\times K_r)\otimes \overline K_s] .\) Theorem 2 gives a \(\it GK\)-decomposition for \(K_3 \times K_r\). Now, we write as \((K_3\times K_r)\otimes \overline K_s\)= \((K \oplus\, K \oplus\,\ldots\,\oplus K) \otimes \overline K_s\) = \((K\otimes\overline K_s) \oplus\, (K\otimes\overline K_s) \oplus \,\ldots \oplus\, (K\otimes\overline K_s).\) A \(\it GK\)-decomposition exists for \(K\otimes\overline K_s\) according to Remark 1. As a consequence of it, a \(\it GK\)-decomposition of \((K_3 \otimes \overline K_n) \times (K_r \otimes \overline K_s)\) has been derived.
Case 2: A \(\it GK\)-decomposition for \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s)\) have been described as follows:
Let \(m \geq 4,\) \(n = 2b,\,b\geq 0\) and for all \(r,\,s,\, (r\neq 2).\) One can obtain a \(\it GK\)-decomposition of \((K_m \otimes \overline K_n)\) from Theorem 1. Then \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s)\) = \((K \oplus K \oplus\,\ldots\,\oplus K)\times (K_r \otimes \overline K_s)\) = \(K\times (K_r \otimes \overline K_s) \oplus K\times (K_r \otimes \overline K_s)\oplus \ldots \oplus K\times (K_r \otimes \overline K_s).\) Now \(K\times (K_r \otimes \overline K_s) \cong (K\times K_r) \otimes \overline K_s.\) A kite decomposition exits for \(K\times K_r\) by using Lemma 1. Moreover, we then write, \((K\times K_r) \otimes \overline K_s\) = \((K \oplus K \oplus\,\ldots\,\oplus K) \otimes \overline K_s\) = \((K\otimes\overline K_s) \oplus (K\otimes\overline K_s) \oplus \ldots \oplus (K\otimes\overline K_s).\) According to Remark 1, a \(\it GK\)-decomposition of \(K\otimes\overline K_s\) has been proved.
Consequently, Cases \(1\) and \(2\) lead a \(\it GK\)-decomposition for \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s)\) when \(n \equiv 0 \pmod 2\) and for all \(m,\,r,\,s,\) \(\{m,\,r \}\neq 2.\) ◻
Lemma 4. A \(\it GK\)-decomposition of \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s)\) exists, if \(n \equiv 1 \pmod 2,\) \(s \equiv 0 \pmod 2,\) and for all \(m,r,\) \(\{m,\,r\} \neq 2.\)
Proof. Case 1: Let \(m = 3,\) \(n = 2b+1,\, b\geq 0,\) \(s= 2c,\, c\geq 0\) and for all \(r,\, (r\neq 2).\) Let us consider \((K_3 \otimes \overline K_n) \times (K_r \otimes \overline K_s) \cong [(K_3 \otimes \overline K_n) \times K_r] \otimes \overline K_s\) = \([(K_3\oplus\, K_3\oplus\, \ldots\oplus\, K_3)\times K_r] \otimes \overline K_s\) = \([(K_3\times K_r)\oplus\,(K_3\times K_r)\oplus\,\ldots \oplus\,(K_3\times K_r)] \otimes \overline K_s\) = \([(K_3\times K_r)\otimes \overline K_s]\oplus\, [(K_3\times K_r)\otimes \overline K_s]\oplus\, \ldots \oplus\, [(K_3\times K_r)\otimes \overline K_s] .\) By Theorem 2, a \(\it GK\)-decomposition exists for \(K_3 \times K_r\). Now \((K_3\times K_r)\otimes \overline K_s\) = \((K \oplus\, K \oplus\,\ldots\,\oplus\, K) \otimes \overline K_s\) = \((K\otimes\overline K_s) \oplus\, (K\otimes\overline K_s) \oplus\, \ldots \oplus\, (K\otimes\overline K_s).\) Now, a \(\it GK\)-decomposition of \(K\otimes\overline K_s\) follows from Remark 1. Thus, the above construction provides a \(\it GK\)-decomposition of \((K_3 \otimes \overline K_n) \times (K_r \otimes \overline K_s)\).
Case 2: Let \(m \geq 4,\) \(n = 2b+1,\, b\geq 0,\) \(s= 2c,\, c\geq 0\) and for all \(r,\, (r\neq 2).\) By Theorem 1, there is a \(\it GK\)-decomposition for \((K_r \otimes \overline K_s)\). Then \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s)\) = \((K_m \otimes \overline K_n)\times (K \oplus K \oplus\,\ldots\,\oplus K)\) = \([(K_m \otimes \overline K_n)\times K] \oplus [(K_m \otimes \overline K_n)\times K]\oplus \ldots \oplus [(K_m \otimes \overline K_n)\times K].\)
Now \([(K_m \otimes \overline K_n)\times K] \cong K\times (K_m \otimes \overline K_n) \cong (K\times K_m) \otimes \overline K_n.\) By Lemma 1, we have a kite decomposition of \(K\times K_m.\) Then \((K\times K_m) \otimes \overline K_n\) = \((K \oplus K \oplus\,\ldots\,\oplus K) \otimes \overline K_n\) = \((K\otimes\overline K_n) \oplus (K\otimes\overline K_n) \oplus \ldots \oplus (K\otimes\overline K_n).\) A \(\it GK\)-decomposition of \(K\otimes \overline K_n\) follows from Remark 1. Thus, all together gives a \(\it GK\)-decomposition of \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s).\) ◻
Lemma 5. A \(\it GK\)-decomposition of \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s)\) exists, if \(m \equiv 4,\,5 \pmod 8,\) \(n,\,s \equiv 1 \pmod 2\) and for all \(r,\) \(r\neq 2.\)
Proof. Let us consider \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s) \cong [(K_m \otimes \overline K_n) \times K_r] \otimes \overline K_s.\) We write as \((K_m \otimes \overline K_n) \times K_r \cong K_r\times(K_m \otimes \overline K_n) \cong (K_r \times K_m)\otimes \overline K_n.\) By Theorem 2, we have a \(\it GK\)-decomposition of \(K_r \times K_m.\) Then \((K_r \times K_m)\otimes \overline K_n\) = \((K \oplus\, K \oplus\,\ldots\,\oplus\, K) \otimes \overline K_n\) = \((K\otimes\overline K_n) \oplus\, (K\otimes\overline K_n) \oplus\, \ldots \oplus\, (K\otimes\overline K_n).\) By Remark 1, we can obtain a \(\it GK\)-decomposition of \(K\otimes \overline K_n.\) Further, \([(K_m \otimes \overline K_n) \times K_r] \otimes \overline K_s\) = \((K \oplus \, K \oplus\,\ldots\,\oplus \, K) \otimes \overline K_s\) = \((K\otimes\overline K_s) \oplus \, (K\otimes\overline K_s) \oplus\, \ldots \oplus\, (K\otimes\overline K_s).\) A \(\it GK\)-decomposition of \(K\otimes \overline K_s\) follows from Remark 1. Thus, all together gives a \(\it GK\)-decomposition of \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s).\) ◻
Lemma 6. A \(\it GK\)-decomposition of \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s)\) exists, if \(m \equiv 2,\,3 \pmod 4,\) \(m\neq 2,\) \(n,\,s \equiv 1 \pmod 2\) and \(r \equiv 0,\,1 \pmod 8.\)
Proof. A \(\it GK\)-decomposition of \(K_r \otimes \overline K_s\) can be obtained from Theorem 1. We then write, \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s)\) = \((K_m \otimes \overline K_n)\times (K \oplus K \oplus\,\ldots\,\oplus K)\) = \([(K_m \otimes \overline K_n)\times K] \oplus [(K_m \otimes \overline K_n)\times K]\oplus \ldots \oplus [(K_m \otimes \overline K_n)\times K].\) Now, we write as \([(K_m \otimes \overline K_n)\times K] \cong K\times (K_m \otimes \overline K_n) \cong (K\times K_m) \otimes \overline K_n.\) A kite decomposition of \(K\times K_m\) has been derived from Lemma 1. Then \((K\times K_m) \otimes \overline K_n\) = \((K \oplus K \oplus\,\ldots\,\oplus K) \otimes \overline K_n\) = \((K\otimes\overline K_n) \oplus (K\otimes\overline K_n) \oplus \ldots \oplus (K\otimes\overline K_n).\) A \(\it GK\)-decomposition of \(K\otimes \overline K_n\) exists according to Remark 1. Consequently, a \(\it GK\)-decomposition exists for \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s)\). ◻
Lemma 7. A \(\it GK\)-decomposition of \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s)\) exists, if \(m \equiv 2,\,3 \pmod 4,\) \(m\neq 2,\) \(n,\,s \equiv 1 \pmod 2\) and \(r \equiv 4,\,5 \pmod 8.\)
Proof. We write \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s) \cong [(K_m \otimes \overline K_n) \times K_r] \otimes \overline K_s.\) Now \((K_m \otimes \overline K_n) \times K_r \cong K_r\times(K_m \otimes \overline K_n) \cong (K_r \times K_m)\otimes \overline K_n.\) By Theorem 2, we have a \(\it GK\)-decomposition of \(K_r \times K_m.\) Then \((K_r \times K_m)\otimes \overline K_n\) = \((K \oplus K \oplus\,\ldots\,\oplus K) \otimes \overline K_n\) = \((K\otimes\overline K_n) \oplus (K\otimes\overline K_n) \oplus \ldots \oplus (K\otimes\overline K_n).\) A \(\it GK\)-decomposition of \(K\otimes \overline K_n\) can be obtained from Remark 1. Further, \([(K_m \otimes \overline K_n) \times K_r] \otimes \overline K_s\) = \((K \oplus K \oplus\,\ldots\,\oplus K) \otimes \overline K_s\) = \((K\otimes\overline K_s) \oplus (K\otimes\overline K_s) \oplus \ldots \oplus (K\otimes\overline K_s)\). A \(\it GK\)-decomposition of \(K\otimes \overline K_s\) follows from Remark 1. Thus the above describes a \(\it GK\)-decomposition for \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s).\) ◻
Theorem 3. There exists a \(\it GK\)-decomposition of \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s)\) if and only if \(n^2 s^2 m(m-1) r(r-1)\equiv 0 \pmod 8.\)
Proof. Necessity: The number of edges of \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s)\) is \(\frac{n^2 s^2 m(m-1) r(r-1)}{2}\) and number of edges of a kite \(K\) is \(4\). Therefore, the edge divisibility condition for a graph \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s)\) is \(\frac{n^2 s^2 m(m-1) r(r-1)}{8}\).
Sufficiency: It has been derived from Lemmas 2 – 7. ◻
In Section 3, we give a complete solution for the existence of a \(\it GK\)-decomposition of \((K_m \otimes \overline K_n) \times (K_r \otimes \overline K_s).\) In future, one can find the existence of a \(\it GK\)-factorization of Tensor product complete multipartite graph.
No funds, grants, or other support were received during preparation of this manuscript.
The author have no conflict of interest.