Extending perfect matchings to Hamiltonian cycles in line graphs

DOI10.37236/9143MaRDI QIDQ2223459zbMATH OpenOpenAlexFDO

Authors M. Abreu, John Baptist Gauci, D. Labbate, G. Mazzuoccolo, Jean Paul Zerafa

Publication date 29 January 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

perfect-matching-Hamiltonian property

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 graph admitting a perfect matching has the Perfect-Matching-Hamiltonian property (for short the PMH-property) if each of its perfect matchings can be extended to a Hamiltonian cycle. In this paper we establish some sufficient conditions for a graph $G$ in order to guarantee that its line graph $L(G)$ has the PMH-property. In particular, we prove that this happens when $G$ is (i) a Hamiltonian graph with maximum degree at most $3$, (ii) a complete graph, or (iii) an arbitrarily traceable graph. Further related questions and open problems are proposed along the paper.

Review text

Summary: A graph admitting a perfect matching has the Perfect-Matching-Hamiltonian property (for short the PMH-property) if each of its perfect matchings can be extended to a Hamiltonian cycle. In this paper we establish some sufficient conditions for a graph \(G\) in order to guarantee that its line graph \(L(G)\) has the PMH-property. In particular, we prove that this happens when \(G\) is (i) a Hamiltonian graph with maximum degree at most \(3\), (ii) a complete graph, or (iii) an arbitrarily traceable graph. Further related questions and open problems are proposed along the paper.

Recommendations

• Perfect matchings, Hamiltonian cycles and edge-colourings in a class of cubic graphs
• Perfect matchings and Hamiltonicity in the Cartesian product of cycles
• scientific article; zbMATH DE number 786151
• On the number of perfect matchings in the line graph of a traceable graph
• The graph of perfect matching polytope and an extreme problem

Cites work

• A degree condition implying that every matching is contained in a Hamiltonian cycle
• A problem regarding the tracing of graphs
• Extending a perfect matching to a Hamiltonian cycle
• Extending matchings in claw-free graphs
• Graph theory
• Graphs with 1-Factors
• Graphs with cycles having adjacent lines different colors
• Graphs with Hamiltonian cycles having adjacent lines different colours
• Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n $
• scientific article; zbMATH DE number 3722690 (Why is no real title available?)
• scientific article; zbMATH DE number 3013445 (Why is no real title available?)
• scientific article; zbMATH DE number 888853 (Why is no real title available?)
• scientific article; zbMATH DE number 3252052 (Why is no real title available?)
• scientific article; zbMATH DE number 3276424 (Why is no real title available?)
• Matchings extend to Hamiltonian cycles in 5-cube
• On Eulerian and Hamiltonian Graphs and Line Graphs
• Perfect matchings extend to Hamilton cycles in hypercubes
• Perfect one-factorizations in line-graphs and planar graphs
• Reflections on graph theory

Cited in

(8)

• Perfect matchings and Hamiltonicity in the Cartesian product of cycles
• On the number of perfect matchings in the line graph of a traceable graph
• Accordion graphs: Hamiltonicity, matchings and isomorphism with quartic circulants
• Betwixt and between 2-factor Hamiltonian and perfect-matching-Hamiltonian graphs
• Perfect matchings, Hamiltonian cycles and edge-colourings in a class of cubic graphs
• Saved by the rook: a case of matchings and Hamiltonian cycles
• Cycle partitions in dense regular digraphs and oriented graphs
• Cycle partition of dense regular digraphs and oriented graphs (extended abstract)

This page was built for publication: Extending perfect matchings to Hamiltonian cycles in line graphs

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