Multi-Decomposition of Product Graphs into Kites and Stars on Four Edges

Abstract

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^\alpha,H_2^\beta\}$-decomposition, if $\alpha$ copies of $H_1$ and $\beta$ copies of $H_2$ decompose $G$, where $\alpha$ and $\beta$ are non-negative integers. In this paper, we have obtained the decomposition of $K_m \times K_n$ into $\alpha$ kites and $\beta$ stars on four edges for some of the admissible pairs $(\alpha,\beta)$, whenever $mn(m-1)(n-1) \equiv 0(mod\ 8)$, for $m \geq 3$ and $n \geq 4$. Also, we have obtained the decomposition of $K_m \otimes \overline{K_n}$ into $\alpha$ kites and $\beta$ stars on four edges for some of the admissible pairs $(\alpha,\beta)$, whenever $m(m-1)n^2 \equiv 0(mod\ 8)$, for $m \geq 3$ and $n \geq 4$. Here $K_m \times K_n$ and $K_m \otimes \overline{K_n}$ respectively denotes the tensor and wreath product of complete graphs.