$C_4$ and $C_6$ decomposition of the tensor product of complete graphs

Abstract

Let $G$ be a simple and finite graph. A graph is said to be \textit{decomposed} into subgraphs $H_1$ and $H_2$ which is denoted by $G=H_1\oplus H_2$, if $G$ is the edge disjoint union of $H_1$ and $H_2$. If $G=H_1\oplus H_2\oplus H_3\oplus \cdots \oplus H_k$, where\ $H_1$,$H_2$,$H_3$, ..., $H_k$ are all isomorphic to $H$, then $G$ is said to be $H$-decomposable. Futhermore, if $H$ is a cycle of length $m$ then we say that $G$ is $C_m$-decomposable and this can be written as $C_m|G$. Where $G\times H$ denotes the tensor product of graphs $G$ and $H$, in this paper, we prove the necessary and sufficient conditions for the existence of $C_4$-decomposition (respectively, $C_6$-decomposition ) of $K_m\times K_n$. Using these conditions it can be shown that every even regular complete multipartite graph $G$ is $C_4$-decomposable (respectively, $C_6$-decomposable) if the number of edges of $G$ is divisible by $4$ (respectively, $6$).

arXiv comment8 pages