On Decompositions of Complete Multipartite Graphs into the Union of two Even Cycles

Abstract

For positive integers $c$ and $d$, let $K_{c\times d}$ denote the complete multipartite graph with $c$ parts, each containing $d$ vertices. Let $G$ with $n$ edges be the union of two vertex-disjoint even cycles. We use graph labelings to show that there exists a cyclic $G$-decomposition of $K_{(2n+1)\times t}$, $K_{(n/2+1)\times 4t}$, $K_{5\times (n/2)t}$, and of $K_{2\times 2nt}$ for every positive integer $t$. If $n\equiv 0(\mathrm{mod}4)$, then there also exists a cyclic $G$-decomposition of $K_{(n+1)\times 2t}$, $K_{(n/4+1)\times 8t}$, $K_{9\times (n/4)t}$, and of $K_{3\times nt}$ for every positive integer $t$.