Perfect matchings and Hamiltonicity in the Cartesian product of cycles

DOI10.1007/S00026-021-00548-1MaRDI QIDQ1981010zbMATH OpenOpenAlexFDO

Authors John Baptist Gauci, Jean Paul Zerafa

Publication date 9 September 2021

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3722690 (Why is no real title available?)
• A degree condition implying that every matching is contained in a Hamiltonian cycle
• Extending a perfect matching to a Hamiltonian cycle
• Extending perfect matchings to Hamiltonian cycles in line graphs
• Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n $
• Matchings extend to Hamiltonian cycles in 5-cube
• On \(F\)-Hamiltonian graphs
• Perfect matchings extend to Hamilton cycles in hypercubes

Cited in

(7)

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

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)