Perfect matchings and Hamiltonicity in the Cartesian product of cycles

preprint2020arXivOpen access

Abstract

A pairing of a graph GG is a perfect matching of the complete graph having the same vertex set as GG. If every pairing of GG can be extended to a Hamiltonian cycle of the underlying complete graph using only edges from GG, then GG has the PH-property. A somewhat weaker property is the PMH-property, whereby every perfect matching of GG can be extended to a Hamiltonian cycle of GG. 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 Cp□CqC_p\square C_q of two cycles on pp and qq vertices does not have the PMH-property, except for C4□C4C_4\square C_4 which is known to have the PH-property.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.