Multi-Decomposition of Product Graphs into Kites and Stars on Four Edges - Velusamy, Jothimani; Palanisamy, Hemalatha (Journal of the Indonesian Mathematical Society, 2025)
A decomposition of a graph $G$ is a set of edge-disjoint subgraphs $H_1,H_2,...,H_r$ of $G$ such that every edge of $G$ belongs to exactly one $H_i$. If all the subgraphs in the decomposition of $G$ are isomorphic to a graph $H$ then we say that $G$ is $H$-decomposable. The graph $G$ has an $\{H_1^α,H_2^β\}$-decomposition, if $α$ copies of $H_1$ and $β$ copies of $H_2$ decompose $G$, where $α$ and $β$ are non-negative integers. In this paper, we have obtained the decomposition of $K_m × K_n$ into $α$ kites and $β$ stars on four edges for some of the admissible pairs $(α,β)$, whenever $mn(m-1)(n-1) \equiv 0(mod\ 8)$, for $m ≥ 3$ and $n ≥ 4$. Also, we have obtained the decomposition of $K_m \otimes \overline{K_n}$ into $α$ kites and $β$ stars on four edges for some of the admissible pairs $(α,β)$, whenever $m(m-1)n^2 \equiv 0(mod\ 8)$, for $m ≥ 3$ and $n ≥ 4$. Here $K_m × K_n$ and $K_m \otimes \overline{K_n}$ respectively denotes the tensor and wreath product of complete graphs.