 Author
 Jan Goedgebeur (UGent) , Barbara Meersman and Carol Zamfirescu (UGent)
 Organization
 Project
 Abstract
 We describe an algorithm for the exhaustive generation of nonisomorphic graphs with a given number k ≥ 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 ≥ 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 4regular 1H graph. Extending work of Schwenk, we describe all orders for which cubic 3H trianglefree 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 4edgeconnected 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.
 Keywords
 Graph Theory, Hamiltonian Cycles, Graph Algorithms
Downloads

(...).pdf
 full text (Published version)
 
 UGent only
 
 
 581.93 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU8644517
 MLA
 Goedgebeur, Jan, et al. “Graphs with Few Hamiltonian Cycles.” MATHEMATICS OF COMPUTATION, vol. 89, no. 322, 2020, pp. 965–91.
 APA
 Goedgebeur, J., Meersman, B., & Zamfirescu, C. (2020). Graphs with few hamiltonian cycles. MATHEMATICS OF COMPUTATION, 89(322), 965–991.
 Chicago authordate
 Goedgebeur, Jan, Barbara Meersman, and Carol Zamfirescu. 2020. “Graphs with Few Hamiltonian Cycles.” MATHEMATICS OF COMPUTATION 89 (322): 965–91.
 Chicago authordate (all authors)
 Goedgebeur, Jan, Barbara Meersman, and Carol Zamfirescu. 2020. “Graphs with Few Hamiltonian Cycles.” MATHEMATICS OF COMPUTATION 89 (322): 965–991.
 Vancouver
 1.Goedgebeur J, Meersman B, Zamfirescu C. Graphs with few hamiltonian cycles. MATHEMATICS OF COMPUTATION. 2020;89(322):965–91.
 IEEE
 [1]J. Goedgebeur, B. Meersman, and C. Zamfirescu, “Graphs with few hamiltonian cycles,” MATHEMATICS OF COMPUTATION, vol. 89, no. 322, pp. 965–991, 2020.
@article{8644517, abstract = {{We describe an algorithm for the exhaustive generation of nonisomorphic graphs with a given number k ≥ 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 ≥ 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 4regular 1H graph. Extending work of Schwenk, we describe all orders for which cubic 3H trianglefree 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 4edgeconnected 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.}}, author = {{Goedgebeur, Jan and Meersman, Barbara and Zamfirescu, Carol}}, issn = {{00255718}}, journal = {{MATHEMATICS OF COMPUTATION}}, keywords = {{Graph Theory,Hamiltonian Cycles,Graph Algorithms}}, language = {{eng}}, number = {{322}}, pages = {{965991}}, title = {{Graphs with few hamiltonian cycles}}, url = {{http://dx.doi.org/10.1090/mcom/3465}}, volume = {{89}}, year = {{2020}}, }
 Altmetric
 View in Altmetric
 Web of Science
 Times cited: