Perfect matchings and Hamiltonicity in the Cartesian product of cycles

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

Authors: 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

Recommendations

• Extending perfect matchings to Hamiltonian cycles in line graphs
• On the hamiltonicity of the Cartesian product
• Betwixt and between 2-factor Hamiltonian and perfect-matching-Hamiltonian graphs
• Perfect matching dominating cycles in some graph products
• On hyper-Hamiltonian Cartesian product of undirected cycles

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

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

Cited In (6)

• Perfect matchings extend to two or more Hamiltonian cycles in hypercubes
• Perfect matching dominating cycles in some graph products
• 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)