Hamiltonian cycles and 1-factors in 5-regular graphs

DOI10.1016/J.JCTB.2021.12.008MaRDI QIDQ2668019zbMATH OpenOpenAlexFDO

Authors Carol T. Zamfirescu, Nico Van Cleemput

Publication date 3 March 2022

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

1-factoredge-colouringHamiltonianplanarregular

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45)

Abstract: It is proven that for any integer $gge0$ and $kin0,ldots,10$, there exist infinitely many 5-regular graphs of genus $g$ containing a 1-factorisation with exactly $k$ pairs of 1-factors that are perfect, i.e. form a hamiltonian cycle. For $g=0$, this settles a problem of Kotzig from 1964. Motivated by Kotzig and Labelle's "marriage" operation, we discuss two gluing techniques aimed at producing graphs of high cyclic edge-connectivity. We prove that there exist infinitely many planar 5-connected 5-regular graphs in which every 1-factorisation has zero perfect pairs. On the other hand, by the Four Colour Theorem and a result of Brinkmann and the first author, every planar 4-connected 5-regular graph satisfying a condition on its hamiltonian cycles has a linear number of 1-factorisations each containing at least one perfect pair. We also prove that every planar 5-connected 5-regular graph satisfying a stronger condition contains a 1-factorisation with at most nine perfect pairs, whence, every such graph admitting a 1-factorisation with ten perfect pairs has at least two edge-Kempe equivalence classes. The paper concludes with further results on edge-Kempe equivalence classes in planar 5-regular graphs.

Recommendations

• Pairs of edge disjoint Hamiltonian circuits in 5-connected planar graphs
• Generating 5-regular planar graphs
• Regular graphs with few longest cycles
• \(4\)-regular \(4\)-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles
• Factorizations of regular graphs

Cites work

• 4-connected polyhedra have at least a linear number of Hamiltonian cycles
• Circuit double cover of graphs
• Counting edge-Kempe-equivalence classes for 3-edge-colored cubic graphs
• Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable
• Edge-colouring eight-regular planar graphs
• Graph edge coloring: a survey
• Grinberg's criterion
• scientific article; zbMATH DE number 5130739 (Why is no real title available?)
• scientific article; zbMATH DE number 3621774 (Why is no real title available?)
• scientific article; zbMATH DE number 3627230 (Why is no real title available?)
• scientific article; zbMATH DE number 7272506 (Why is no real title available?)
• scientific article; zbMATH DE number 3276424 (Why is no real title available?)
• scientific article; zbMATH DE number 3295346 (Why is no real title available?)
• Kempe equivalence of edge-colorings in subcubic and subquartic graphs
• On Hamilton cycles in certain planar graphs
• Pairs of edge disjoint Hamiltonian circuits in 5-connected planar graphs
• Pairs of Hamiltonian circuits in 5-connected planar graphs
• Perfect one-factorizations in line-graphs and planar graphs
• Recursive generation of simple planar 5-regular graphs and pentangulations
• Solution of Vizing's problem on interchanges for the case of graphs with maximum degree 4 and related results

Cited in

(2)

• Pairs of edge disjoint Hamiltonian circuits in 5-connected planar graphs
• scientific article; zbMATH DE number 5239125 (Why is no real title available?)

This page was built for publication: Hamiltonian cycles and 1-factors in 5-regular graphs

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