$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 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 \cdots \oplus H_k$, where $H_1,H_2,\dots ,H_k$ are all isomorphic to $H$, then $G$ is said to be $H$-decomposable. Furthermore, 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\mid G$. Where $G\times H$ denotes the tensor product of graphs $G$ and $H$, in this paper, we prove that the necessary conditions for the existence of $C_6$-decomposition of $K_m\times K_n$ are sufficient. Using these conditions it can be shown that every even regular complete multipartite graph $G$ is $C_6$-decomposable if the number of edges of $G$ is divisible by 6.