C6-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 \dots \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.