Perfect matchings and Hamiltonicity in the Cartesian product of cycles

Abstract

A pairing of a graph $G$ is a perfect matching of the complete graph having the same vertex set as $G$. If every pairing of $G$ can be extended to a Hamiltonian cycle of the underlying complete graph using only edges from $G$, then $G$ has the PH-property. A somewhat weaker property is the PMH-property, whereby every perfect matching of $G$ can be extended to a Hamiltonian cycle of $G$. In an attempt to characterise all 4-regular graphs having the PH-property, we answer a question made in 2015 by Alahmadi et al. by showing that the Cartesian product $C_p\square C_q$ of two cycles on $p$ and $q$ vertices does not have the PMH-property, except for $C_4\square C_4$ which is known to have the PH-property.

arXiv comment6 pages, 2 figures

References in corpus (1)

• Extending perfect matchings to Hamiltonian cycles in line graphs

Cited by in corpus (3)

• Accordion graphs: Hamiltonicity, matchings and isomorphism with quartic circulants
• The Pairing-Hamiltonian property in graph prisms
• Perfect matchings, Hamiltonian cycles and edge-colourings in a class of cubic graphs