Graphs with few Hamiltonian cycles

DOI10.1090/MCOM/3465zbMATH Open1429.05114arXiv1812.05650OpenAlexW2905023271MaRDI QIDQ5207451FDOQ5207451

Authors: Jan Goedgebeur, Barbara Meersman, Carol T. Zamfirescu 

Publication date: 27 December 2019

Published in: Mathematics of Computation (Search for Journal in Brave)

Abstract: We describe an algorithm for the exhaustive generation of non-isomorphic graphs with a given number $kge0$ of hamiltonian cycles, which is especially efficient for small $k$. Our main findings, combining applications of this algorithm and existing algorithms with new theoretical results, revolve around graphs containing exactly one hamiltonian cycle (1H) or exactly three hamiltonian cycles (3H). Motivated by a classic result of Smith and recent work of Royle, we show that there exist nearly cubic 1H graphs of order $n$ iff $nge18$ is even. This gives the strongest form of a theorem of Entringer and Swart, and sheds light on a question of Fleischner originally settled by Seamone. We prove equivalent formulations of the conjecture of Bondy and Jackson that every planar 1H graph contains two vertices of degree 2, verify it up to order 16, and show that its toric analogue does not hold. We treat Thomassen's conjecture that every hamiltonian graph of minimum degree at least $3$ contains an edge such that both its removal and its contraction yield hamiltonian graphs. We also verify up to order 21 the conjecture of Sheehan that there is no 4-regular 1H graph. Extending work of Schwenk, we describe all orders for which cubic 3H triangle-free graphs exist. We verify up to order $48$ Cantoni's conjecture that every planar cubic 3H graph contains a triangle, and show that there exist infinitely many planar cyclically 4-edge-connected cubic graphs with exactly four hamiltonian cycles, thereby answering a question of Chia and Thomassen. Finally, complementing work of Sheehan on 1H graphs of maximum size, we determine the maximum size of graphs containing exactly one hamiltonian path and give, for every order $n$, the exact number of such graphs on $n$ vertices and of maximum size.

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

Recommendations

• scientific article; zbMATH DE number 1185588
• A lower bound for the smallest uniquely Hamiltonian planar graph with minimum degree three
• Hamiltonian cycles in cubic 3-connected bipartite planar graphs
• Hamiltonian cycles in some family of cubic 3-connected plane graphs
• scientific article; zbMATH DE number 1488848

zbMATH Keywords

Hamiltonian cyclecubic graphgirthexhaustive generationuniquely HamiltonianBondy-Jackson conjectureuniquely traceable

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Cites Work

• House of Graphs: a database of interesting graphs
• Title not available (Why is that?)
• Practical graph isomorphism. II.
• Generation of cubic graphs
• Fast generation of regular graphs and construction of cages
• Fast generation of planar graphs
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• Enumeration of Hamiltonian cycles in certain generalized Petersen graphs
• Isomorph-Free Exhaustive Generation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generation of cubic graphs and snarks with large girth
• Independent dominating sets and hamiltonian cycles
• On Hamiltonian Circuits
• On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
• On the minimum number of Hamiltonian cycles in regular graphs
• Independent dominating sets and a second hamiltonian cycle in regular graphs
• On uniquely Hamiltonian claw-free and triangle-free graphs
• On the number of Hamiltonian cycles in bipartite graphs
• Title not available (Why is that?)
• Spanning cycles of nearly cubic graphs
• Planar cubic hypohamiltonian and hypotraceable graphs
• Graphs with exactly one hamiltonian circuit
• A census of maximum uniquely hamiltonian graphs
• Highly-connected planar cubic graphs with few or many Hamilton cycles
• Vertices of small degree in uniquely Hamiltonian graphs
• A degree constraint for uniquely Hamiltonian graphs
• On the number of longest and almost longest cycles in cubic graphs.
• Uniquely Hamiltonian graphs of minimum degree 4
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (12)

• Regular graphs with few longest cycles
• Title not available (Why is that?)
• Improved asymptotic upper bounds for the minimum number of longest cycles in regular graphs
• Few Hamiltonian cycles in graphs with one or two vertex degrees
• A lower bound for the smallest uniquely Hamiltonian planar graph with minimum degree three
• On interval transmission irregular graphs
• Hamiltonian path saturated graphs with small size
• Complete symmetry breaking constraints for the class of uniquely Hamiltonian graphs
• Switching 3-edge-colorings of cubic graphs
• K₂‐Hamiltonian graphs: II
• Title not available (Why is that?)
• \(4\)-regular \(4\)-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles

Uses Software

• nauty
• House of Graphs
• OEIS
• Traces
• plantri
• MathOverflow
• GENREG
• GenerateUHG
• snarkhunter

This page was built for publication: Graphs with few Hamiltonian cycles

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