Graphs with few hamiltonian cycles
HTML articles powered by AMS MathViewer
- by Jan Goedgebeur, Barbara Meersman and Carol T. Zamfirescu HTML | PDF
- Math. Comp. 89 (2020), 965-991 Request permission
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
- Sarmad Abbasi and Asif Jamshed, A degree constraint for uniquely Hamiltonian graphs, Graphs Combin. 22 (2006), no. 4, 433–442. MR 2270365, DOI 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 10.1002/jgt.3190050313
- Claude Berge, Graphs and hypergraphs, North-Holland Mathematical Library, Vol. 6, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. Translated from the French by Edward Minieka. 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 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 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 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 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 10.1016/0095-8956(80)90087-8
- Herbert Fleischner, Uniquely Hamiltonian graphs of minimum degree 4, J. Graph Theory 75 (2014), no. 2, 167–177. MR 3150571, DOI 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 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 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 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 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 10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G
- Julius Petersen, Die Theorie der regulären graphs, Acta Math. 15 (1891), no. 1, 193–220 (German). MR 1554815, DOI 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 10.1016/0095-8956(89)90064-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 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 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 10.1016/0095-8956(81)90089-7
- Carsten Thomassen, On the number of Hamiltonian cycles in bipartite graphs, Combin. Probab. Comput. 5 (1996), no. 4, 437–442. MR 1426436, DOI 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 10.1006/jctb.1997.1794
- W. T. Tutte, On Hamiltonian circuits, J. London Math. Soc. 21 (1946), 98–101. MR 19300, DOI 10.1112/jlms/s1-21.2.98
- William T. Tutte, Hamiltonian circuits, Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973) Atti dei Convegni Lincei, No. 17, Accad. Naz. Lincei, Rome, 1976, pp. 193–199 (English, with Italian summary). MR 0480185
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
- 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)
- © Copyright 2019 American Mathematical Society
- Journal: Math. Comp. 89 (2020), 965-991
- MSC (2010): Primary 05C10, 05C45, 05C85; Secondary 05C38
- DOI: https://doi.org/10.1090/mcom/3465
- MathSciNet review: 4044458