Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Graphs with few hamiltonian cycles


Authors: Jan Goedgebeur, Barbara Meersman and Carol T. Zamfirescu
Journal: Math. Comp.
MSC (2010): Primary 05C10, 05C45, 05C85; Secondary 05C38
DOI: https://doi.org/10.1090/mcom/3465
Published electronically: September 5, 2019
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: We describe an algorithm for the exhaustive generation of non-isomorphic graphs with a given number $ k \ge 0$ 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 $ n \ge 18$ 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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 05C10, 05C45, 05C85, 05C38

Retrieve articles in all journals with MSC (2010): 05C10, 05C45, 05C85, 05C38


Additional Information

Jan Goedgebeur
Affiliation: Department of Applied Mathematics, Computer Science & Statistics, Ghent University, Krijgslaan 281-S9, 9000 Ghent, Belgium; and Computer Science Department, University of Mons, Place du Parc 20, 7000 Mons, Belgium
Email: jan.goedgebeur@ugent.be

Barbara Meersman
Affiliation: Department of Applied Mathematics, Computer Science & Statistics, Ghent University, Krijgslaan 281-S9, 9000 Ghent, Belgium
Email: barbara.meersman@ugent.be

Carol T. Zamfirescu
Affiliation: Department of Applied Mathematics, Computer Science & Statistics, Ghent University, Krijgslaan 281-S9, 9000 Ghent, Belgium; and Department of Mathematics, Babeş-Bolyai University, Cluj-Napoca, Roumania
Email: czamfirescu@gmail.com

DOI: https://doi.org/10.1090/mcom/3465
Keywords: Hamiltonian cycle, uniquely hamiltonian, uniquely traceable, Bondy-Jackson conjecture, cubic graph, girth, exhaustive generation
Received by editor(s): December 17, 2018
Received by editor(s) in revised form: May 8, 2019
Published electronically: September 5, 2019
Additional Notes: The first and third authors were supported by a Postdoctoral Fellowship of the Research Foundation Flanders (FWO)
Article copyright: © Copyright 2019 American Mathematical Society