On Hamilton Cycle Decompositions of Tensor Products of Graphs

Abstract

A Hamiltonian decomposition of $G$ is a partition of its edge set into disjoint Hamilton cycles. Manikandan and Paulraja conjectured that if $G$ and $H$ are Hamilton cycle decomposable circulant graphs with at least one of them is nonbipartite, then their tensor product is Hamilton cycle decomposable. In this paper, we have proved that, if $G$ is a Hamilton cycle decomposable circulant graph with certain properties and $H$ is a Hamilton cycle decomposable multigraph, then their tensor product is Hamilton cycle decomposable. In particular, tensor products of certain sparse Hamilton cycle decomposable circulant graphs are Hamilton cycle decomposable.

24 pages, 13 figures