Graphs with few Hamiltonian cycles

DOI10.1090/MCOM/3465MaRDI QIDQ5207451zbMATH OpenOpenAlexFDO

Authors Jan Goedgebeur, Barbara Meersman, Carol T. Zamfirescu

Publication date 27 December 2019

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

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

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)

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.

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

Cites work

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

Cited in

(12)

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

Describes a project that uses

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)