Hamiltonian Cycle Decomposition of Kronecker Product of Some Cubic Graphs by Cycles

Abstract

A graph is said $h$-decomposable if its edge-set is decomposable into hamiltonian cycles. In this paper, we prove that if $G=L_1\cup L_2\cup L_3$ is a strongly hamiltonian bipartite cubic graph (where $L_i$ is a perfect matching, for $1\le i\le 3$ and $(L_1,L_2,L_3)$ is a $1$-factorization of $G$), then $G\times C_{2n+1}$ (where $n$ is odd and $n\ge 1$) is decomposable. As a corollary, we show that for $r\ge 1$ odd and $n\ge 3$, $K_{r,r}\times K_n$ is $h$-decomposable. Moreover, in the case where $G$ is a strongly hamiltonian non-bipartite cubic graph, we prove that the same result can be derived using a special perfect matching. Hence $K_{2r}\times K_{2n+1}$ will be $h$-decomposable, for $r,n\ge 1$.

To study the product of $G=L_1\cup L_2\cup L_3$ by even cycle, we define a dual graph $G_C$ based on an alternating cycle subset of $L_2\cup L_3$. We show that if a non-bipartite cubic graph $G=L_1\cup L_2\cup L_3$, with $|V(G)|=2m$, admits $L_1\cup L_2$ as a hamiltonian cycle and $G_C$ is connected, then $G\times K_2$ is hamiltonian and $G\times C_{2n}$ has two edge-disjoint hamiltonian cycles. Finally, we prove that if $C=L_2\cup L_3$ and $L_1\cup L_3$ admits a particular alternating $4$-cycle $C^{\prime }$, then $G\times C_{2n}$ is $h$-decomposable.