Graphs with few Hamiltonian cycles. (English) Zbl 1429.05114

Goedgebeur, Jan; Meersman, Barbara; Zamfirescu, Carol T.

Math. Comput. 89, No. 322, 965-991 (2020).

Summary: 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 [see [W. T. Tutte, J. Lond. Math. Soc. 21, 98–101 (1946; Zbl 0061.41306)]) 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 R. C. Entringer and H. Swart [J. Comb. Theory, Ser. B 29, 303–309 (1980; Zbl 0387.05017)], and sheds light on a question of H. Fleischner [J. Graph Theory 75, No. 2, 167–177 (2014; Zbl 1280.05074)] originally settled by B. Seamone [Discuss. Math., Graph Theory 35, No. 2, 207–214 (2015; Zbl 1311.05104)]. We prove equivalent formulations of the conjecture of J. A. Bondy and B. Jackson [J. Comb. Theory, Ser. B 74, No. 2, 265–275 (1998; Zbl 1026.05071)] 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 J. Sheehan [J. Graph Theory 1, 37–43 (1977; Zbl 0359.05026)] that there is no 4-regular 1H graph. Extending work of A. J. Schwenk [J. Comb. Theory, Ser. B 47, No. 1, 53–59 (1989; Zbl 0626.05038)], 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 eneralized Petersen graph G. L. Chia and C. Thomassen [Ars Comb. 104, 307–320 (2012; Zbl 1274.05254)]. Finally, complementing work of J. Sheehan [loc. cit.] 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.

MSC:

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

Keywords:

Hamiltonian cycle; uniquely Hamiltonian; uniquely traceable; Bondy-Jackson conjecture; cubic graph; girth; exhaustive generation

Citations:

Zbl 0061.41306; Zbl 0387.05017; Zbl 1280.05074; Zbl 1311.05104; Zbl 1026.05071; Zbl 0359.05026; Zbl 0626.05038; Zbl 1274.05254

Software:

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

References:

[1]	Abbasi, Sarmad; Jamshed, Asif, A degree constraint for uniquely Hamiltonian graphs, Graphs Combin., 22, 4, 433-442 (2006) · Zbl 1118.05055
[2]	Barefoot, Curtiss A.; Entringer, R. C., A census of maximum uniquely Hamiltonian graphs, J. Graph Theory, 5, 3, 315-321 (1981) · Zbl 0462.05045
[3]	Berge, Claude, Graphs and Hypergraphs, xiv+528 pp. (1973), North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York · Zbl 0254.05101
[4]	Bondy, J. A.; Jackson, Bill, Vertices of small degree in uniquely Hamiltonian graphs, J. Combin. Theory Ser. B, 74, 2, 265-275 (1998) · Zbl 1026.05071
[5]	Boyer, John M.; Myrvold, Wendy J., On the cutting edge: simplified \(O(n)\) planarity by edge addition, J. Graph Algorithms Appl., 8, 3, 241-273 (2004) · Zbl 1086.05067
[6]	Brinkmann, Gunnar; Coolsaet, Kris; Goedgebeur, Jan; M\'{e}lot, Hadrien, House of Graphs: a database of interesting graphs, Discrete Appl. Math., 161, 1-2, 311-314 (2013) · Zbl 1292.05254
[7]	Brinkmann, Gunnar; Goedgebeur, Jan, Generation of cubic graphs and snarks with large girth, J. Graph Theory, 86, 2, 255-272 (2017) · Zbl 1370.05198
[8]	Brinkmann, Gunnar; Goedgebeur, Jan; McKay, Brendan D., Generation of cubic graphs, Discrete Math. Theor. Comput. Sci., 13, 2, 69-79 (2011) · Zbl 1283.05256
[9]	Brinkmann, Gunnar; McKay, Brendan D., Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem., 58, 2, 323-357 (2007) · Zbl 1164.68025
[10]	Chia, Gek L.; Thomassen, Carsten, On the number of longest and almost longest cycles in cubic graphs, Ars Combin., 104, 307-320 (2012) · Zbl 1274.05254
[11]	Chia, G. L.; Yu, Qinglin R., On the number of Hamilton cycles in cubic graphs, Congr. Numer.. Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995), 110, 13-32 (1995) · Zbl 0904.05043
[12]	Entringer, R. C.; Swart, Henda, Spanning cycles of nearly cubic graphs, J. Combin. Theory Ser. B, 29, 3, 303-309 (1980) · Zbl 0387.05017
[13]	Fleischner, Herbert, Uniquely Hamiltonian graphs of minimum degree 4, J. Graph Theory, 75, 2, 167-177 (2014) · Zbl 1280.05074
[14]	Fowler, Thomas George, Unique coloring of planar graphs, 191 pp. (1998), ProQuest LLC, Ann Arbor, MI
[15]	genUHG-site J. Goedgebeur, B. Meersman, and C. T. Zamfirescu, Homepage of genhypohamiltonian: http://caagt.ugent.be/uhg/.
[16]	grinberg1986three 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.
[17]	Haxell, Penny; Seamone, Ben; Verstraete, Jacques, Independent dominating sets and Hamiltonian cycles, J. Graph Theory, 54, 3, 233-244 (2007) · Zbl 1112.05077
[18]	Haythorpe, M., On the minimum number of Hamiltonian cycles in regular graphs, Exp. Math., 27, 4, 426-430 (2018) · Zbl 1403.05082
[19]	Holton, Derek; Aldred, Robert E. L., Planar graphs, regular graphs, bipartite graphs and Hamiltonicity, Australas. J. Combin., 20, 111-131 (1999) · Zbl 0931.05046
[20]	nauty-website 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.
[21]	McKay, Brendan D., Isomorph-free exhaustive generation, J. Algorithms, 26, 2, 306-324 (1998) · Zbl 0894.68107
[22]	McKay, Brendan D.; Piperno, Adolfo, Practical graph isomorphism, II, J. Symbolic Comput., 60, 94-112 (2014) · Zbl 1394.05079
[23]	Meringer, Markus, Fast generation of regular graphs and construction of cages, J. Graph Theory, 30, 2, 137-146 (1999) · Zbl 0918.05062
[24]	Petersen, Julius, Die Theorie der regul\"{a}ren graphs, Acta Math., 15, 1, 193-220 (1891) · JFM 23.0115.03
[25]	pivotto2019 I. Pivotto and G. Royle, Highly-connected planar cubic graphs with few or many Hamilton cycles, https://arxiv.org/abs/1901.10683. · Zbl 1422.05059
[26]	Ro17 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.
[27]	Schwenk, Allen J., Enumeration of Hamiltonian cycles in certain generalized Petersen graphs, J. Combin. Theory Ser. B, 47, 1, 53-59 (1989) · Zbl 0626.05038
[28]	Seamone, Ben, On uniquely Hamiltonian claw-free and triangle-free graphs, Discuss. Math. Graph Theory, 35, 2, 207-214 (2015) · Zbl 1311.05104
[29]	Sheehan, John, The multiplicity of Hamiltonian circuits in a graph. Recent advances in graph theory, Proc. Second Czechoslovak Sympos., Prague, 1974, 477-480 (1975), Academia, Prague
[30]	Sheehan, John, Graphs with exactly one Hamiltonian circuit, J. Graph Theory, 1, 1, 37-43 (1977) · Zbl 0359.05026
[31]	OEIS N. Sloane, The on-line encyclopedia of integer sequences, http://oeis.org/. · Zbl 1044.11108
[32]	Thomason, A. G., Hamiltonian cycles and uniquely edge colourable graphs, Ann. Discrete Math., 3, 259-268 (1978) · Zbl 0382.05039
[33]	Thomassen, Carsten, Planar cubic hypo-Hamiltonian and hypotraceable graphs, J. Combin. Theory Ser. B, 30, 1, 36-44 (1981) · Zbl 0388.05033
[34]	Thomassen, Carsten, On the number of Hamiltonian cycles in bipartite graphs, Combin. Probab. Comput., 5, 4, 437-442 (1996) · Zbl 0868.05034
[35]	Thomassen, Carsten, Independent dominating sets and a second Hamiltonian cycle in regular graphs, J. Combin. Theory Ser. B, 72, 1, 104-109 (1998) · Zbl 0895.05038
[36]	Tutte, W. T., On Hamiltonian circuits, J. London Math. Soc., 21, 98-101 (1946) · Zbl 0061.41306
[37]	Tutte, William T., Hamiltonian circuits. Colloquio Internazionale sulle Teorie Combinatorie, Rome, 1973, 193-199. Atti dei Convegni Lincei, No. 17 (1976), Accad. Naz. Lincei, Rome