C_4 decomposition of the tensor product of complete graphs

Opeyemi Oyewumi (General Studies Department, Air Force Institute of Technology, Kaduna, Nigeria)
Abolape Deborah Akwu (Department of Mathematics, Federal University of Agriculture, Makurdi, Nigeria)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 8, No 1 (2020): Electronic Journal of Graph Theory and Applications

Let G be a simple and finite graph. A graph is said to be decomposed into subgraphs H1 and H2 which is denoted by G = H1 ⊕ H2, if G is the edge disjoint union of H1 and H2. If G = H1 ⊕ H2 ⊕ H3 ⊕ ... ⊕ Hk, where H1, H2, H3, ..., Hk 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 Cm-decomposable and this can be written as Cm|G. Where G × H denotes the tensor product of graphs G and H, in this paper, we prove the necessary and sufficient conditions for the existence of C4-decomposition of Km × Kn. Using these conditions it can be shown that every even regular complete multipartite graph G is  C4-decomposable if the number of edges of G is divisible by 4.