On Hamilton Cycle Decompositions of Tensor Products of Graphs

arXiv1703.03148MaRDI QIDQ6284098FDOQ6284098

Authors: P. Paulraja, S. Sampath Kumar 

Publication date: 9 March 2017

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.

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graph operations (line graphs, products, etc.) (05C76)

This page was built for publication: On Hamilton Cycle Decompositions of Tensor Products of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6284098)