Graphs with few hamiltonian cycles
Authors:
Jan Goedgebeur, Barbara Meersman and Carol T. Zamfirescu
Journal:
Math. Comp. 89 (2020), 965-991
MSC (2010):
Primary 05C10, 05C45, 05C85; Secondary 05C38
DOI:
https://doi.org/10.1090/mcom/3465
Published electronically:
September 5, 2019
MathSciNet review:
4044458
Full-text PDF
View in AMS MathViewer
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.
- Sarmad Abbasi and Asif Jamshed, A degree constraint for uniquely Hamiltonian graphs, Graphs Combin. 22 (2006), no. 4, 433–442. MR 2270365, DOI https://doi.org/10.1007/s00373-006-0666-z
- Curtiss A. Barefoot and R. C. Entringer, A census of maximum uniquely Hamiltonian graphs, J. Graph Theory 5 (1981), no. 3, 315–321. MR 625073, DOI https://doi.org/10.1002/jgt.3190050313
- Claude Berge, Graphs and hypergraphs, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. Translated from the French by Edward Minieka; North-Holland Mathematical Library, Vol. 6. MR 0357172
- J. A. Bondy and Bill Jackson, Vertices of small degree in uniquely Hamiltonian graphs, J. Combin. Theory Ser. B 74 (1998), no. 2, 265–275. MR 1654125, DOI https://doi.org/10.1006/jctb.1998.1845
- John M. Boyer and Wendy J. Myrvold, On the cutting edge: simplified $O(n)$ planarity by edge addition, J. Graph Algorithms Appl. 8 (2004), no. 3, 241–273. MR 2166815, DOI https://doi.org/10.7155/jgaa.00091
- Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur, and Hadrien Mélot, House of Graphs: a database of interesting graphs, Discrete Appl. Math. 161 (2013), no. 1-2, 311–314. MR 2973372, DOI https://doi.org/10.1016/j.dam.2012.07.018
- Gunnar Brinkmann and Jan Goedgebeur, Generation of cubic graphs and snarks with large girth, J. Graph Theory 86 (2017), no. 2, 255–272. MR 3684787, DOI https://doi.org/10.1002/jgt.22125
- Gunnar Brinkmann, Jan Goedgebeur, and Brendan D. McKay, Generation of cubic graphs, Discrete Math. Theor. Comput. Sci. 13 (2011), no. 2, 69–79. MR 2820891
- Gunnar Brinkmann and Brendan D. McKay, Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem. 58 (2007), no. 2, 323–357. MR 2357364
- Gek L. Chia and Carsten Thomassen, On the number of longest and almost longest cycles in cubic graphs, Ars Combin. 104 (2012), 307–320. MR 2951794
- G. L. Chia and Qinglin R. Yu, On the number of Hamilton cycles in cubic graphs, Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995), 1995, pp. 13–32. MR 1369314
- R. C. Entringer and Henda Swart, Spanning cycles of nearly cubic graphs, J. Combin. Theory Ser. B 29 (1980), no. 3, 303–309. MR 602422, DOI https://doi.org/10.1016/0095-8956%2880%2990087-8
- Herbert Fleischner, Uniquely Hamiltonian graphs of minimum degree 4, J. Graph Theory 75 (2014), no. 2, 167–177. MR 3150571, DOI https://doi.org/10.1002/jgt.21729
- Thomas George Fowler, Unique coloring of planar graphs, ProQuest LLC, Ann Arbor, MI, 1998. Thesis (Ph.D.)–Georgia Institute of Technology. MR 2698714
- J. Goedgebeur, B. Meersman, and C. T. Zamfirescu, Homepage of genhypohamiltonian: http://caagt.ugent.be/uhg/.
- E. Grinberg, Three-connected graphs with exactly one Hamiltonian cycle (in Russian), Republican Foundation of Algorithms and Programmes. Computing centre, P. Stutschka University, Riga, USSR, 1986.
- Penny Haxell, Ben Seamone, and Jacques Verstraete, Independent dominating sets and Hamiltonian cycles, J. Graph Theory 54 (2007), no. 3, 233–244. MR 2290229, DOI https://doi.org/10.1002/jgt.20205
- M. Haythorpe, On the minimum number of Hamiltonian cycles in regular graphs, Exp. Math. 27 (2018), no. 4, 426–430. MR 3894721, DOI https://doi.org/10.1080/10586458.2017.1306813
- Derek Holton and Robert E. L. Aldred, Planar graphs, regular graphs, bipartite graphs and Hamiltonicity, Australas. J. Combin. 20 (1999), 111–131. MR 1723867
- B. D. McKay, nauty User’s Guide (Version 2.5). Technical Report TR-CS-90-02, Department of Computer Science, Australian National University. The latest version of the software is available at http://cs.anu.edu.au/~bdm/nauty.
- Brendan D. McKay, Isomorph-free exhaustive generation, J. Algorithms 26 (1998), no. 2, 306–324. MR 1606516, DOI https://doi.org/10.1006/jagm.1997.0898
- Brendan D. McKay and Adolfo Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014), 94–112. MR 3131381, DOI https://doi.org/10.1016/j.jsc.2013.09.003
- Markus Meringer, Fast generation of regular graphs and construction of cages, J. Graph Theory 30 (1999), no. 2, 137–146. MR 1665972, DOI https://doi.org/10.1002/%28SICI%291097-0118%28199902%2930%3A2%3C137%3A%3AAID-JGT7%3E3.0.CO%3B2-G
- Julius Petersen, Die Theorie der regulären graphs, Acta Math. 15 (1891), no. 1, 193–220 (German). MR 1554815, DOI https://doi.org/10.1007/BF02392606
- I. Pivotto and G. Royle, Highly-connected planar cubic graphs with few or many Hamilton cycles, https://arxiv.org/abs/1901.10683.
- G. F. Royle, The smallest uniquely hamiltonian graph with minimum degree at least 3, https://mathoverflow.net/questions/255784/what-is-the-smallest-uniquely-hamiltonian-graph-with-minimum-degree-at-least-3/, 2017.
- Allen J. Schwenk, Enumeration of Hamiltonian cycles in certain generalized Petersen graphs, J. Combin. Theory Ser. B 47 (1989), no. 1, 53–59. MR 1007713, DOI https://doi.org/10.1016/0095-8956%2889%2990064-6
- Ben Seamone, On uniquely Hamiltonian claw-free and triangle-free graphs, Discuss. Math. Graph Theory 35 (2015), no. 2, 207–214. MR 3338746, DOI https://doi.org/10.7151/dmgt.1784
- John Sheehan, The multiplicity of Hamiltonian circuits in a graph, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974) Academia, Prague, 1975, pp. 477–480. MR 0398896
- John Sheehan, Graphs with exactly one Hamiltonian circuit, J. Graph Theory 1 (1977), no. 1, 37–43. MR 460180, DOI https://doi.org/10.1002/jgt.3190010110
- N. Sloane, The on-line encyclopedia of integer sequences, http://oeis.org/.
- A. G. Thomason, Hamiltonian cycles and uniquely edge colourable graphs, Ann. Discrete Math. 3 (1978), 259–268. MR 499124
- Carsten Thomassen, Planar cubic hypo-Hamiltonian and hypotraceable graphs, J. Combin. Theory Ser. B 30 (1981), no. 1, 36–44. MR 609592, DOI https://doi.org/10.1016/0095-8956%2881%2990089-7
- Carsten Thomassen, On the number of Hamiltonian cycles in bipartite graphs, Combin. Probab. Comput. 5 (1996), no. 4, 437–442. MR 1426436, DOI https://doi.org/10.1017/S0963548300002182
- Carsten Thomassen, Independent dominating sets and a second Hamiltonian cycle in regular graphs, J. Combin. Theory Ser. B 72 (1998), no. 1, 104–109. MR 1604697, DOI https://doi.org/10.1006/jctb.1997.1794
- W. T. Tutte, On Hamiltonian circuits, J. London Math. Soc. 21 (1946), 98–101. MR 19300, DOI https://doi.org/10.1112/jlms/s1-21.2.98
- William T. Tutte, Hamiltonian circuits, Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973) Accad. Naz. Lincei, Rome, 1976, pp. 193–199. Atti dei Convegni Lincei, No. 17 (English, with Italian summary). MR 0480185
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
MR Author ID:
945364
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
MR Author ID:
756214
Email:
czamfirescu@gmail.com
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