Perfect matchings and Hamiltonicity in the Cartesian product of cycles

DOI10.1007/S00026-021-00548-1zbMATH Open1472.05126arXiv2005.02913OpenAlexW3193161769MaRDI QIDQ1981010FDOQ1981010

John Baptist Gauci, Jean Paul Zerafa

Publication date: 9 September 2021

Published in: Annals of Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2005.02913

zbMATH Keywords

Hamiltonian cycleperfect matchingCartesian product of cycles

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Perfect matchings extend to Hamilton cycles in hypercubes
• Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n $
• On \(F\)-Hamiltonian graphs
• A degree condition implying that every matching is contained in a Hamiltonian cycle
• Matchings extend to Hamiltonian cycles in 5-cube
• Extending perfect matchings to Hamiltonian cycles in line graphs

Cited In (5)

• Perfect matchings extend to two or more Hamiltonian cycles in hypercubes
• Perfect matchings, Hamiltonian cycles and edge-colourings in a class of cubic graphs
• Betwixt and between 2-factor Hamiltonian and perfect-matching-Hamiltonian graphs
• Accordion graphs: Hamiltonicity, matchings and isomorphism with quartic circulants
• Perfect matchings extend to Hamilton cycles in hypercubes

This page was built for publication: Perfect matchings and Hamiltonicity in the Cartesian product of cycles

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