{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T04:07:50Z","timestamp":1776830870154,"version":"3.51.2"},"reference-count":37,"publisher":"American Mathematical Society (AMS)","issue":"322","license":[{"start":{"date-parts":[[2020,9,5]],"date-time":"2020-09-05T00:00:00Z","timestamp":1599264000000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/501100003130","name":"Fonds Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003130","name":"Fonds Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    We describe an algorithm for the exhaustive generation of non-isomorphic graphs with a given number\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"k greater-than-or-equal-to 0\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mo>\n                              \u2265\n                              \n                            <\/mml:mo>\n                            <mml:mn>0<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">k \\ge 0<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    of hamiltonian cycles, which is especially efficient for small\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"k\">\n                        <mml:semantics>\n                          <mml:mi>k<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">k<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . 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                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n\">\n                        <mml:semantics>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    iff\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n greater-than-or-equal-to 18\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>\n                              \u2265\n                              \n                            <\/mml:mo>\n                            <mml:mn>18<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">n \\ge 18<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    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\u00a02, verify it up to order\u00a016, and show that its toric analogue does not hold. We treat Thomassen\u2019s conjecture that every hamiltonian graph of minimum degree at least\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"3\">\n                        <mml:semantics>\n                          <mml:mn>3<\/mml:mn>\n                          <mml:annotation encoding=\"application\/x-tex\">3<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    contains an edge such that both its removal and its contraction yield hamiltonian graphs. We also verify up to order\u00a021 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\u00a0\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"48\">\n                        <mml:semantics>\n                          <mml:mn>48<\/mml:mn>\n                          <mml:annotation encoding=\"application\/x-tex\">48<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    Cantoni\u2019s 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                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n\">\n                        <mml:semantics>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , the exact number of such graphs on\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n\">\n                        <mml:semantics>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    vertices and of maximum size.\n                  <\/p>","DOI":"10.1090\/mcom\/3465","type":"journal-article","created":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T10:12:28Z","timestamp":1560334348000},"page":"965-991","source":"Crossref","is-referenced-by-count":10,"title":["Graphs with few hamiltonian cycles"],"prefix":"10.1090","volume":"89","author":[{"given":"Jan","family":"Goedgebeur","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Barbara","family":"Meersman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carol","family":"Zamfirescu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2019,9,5]]},"reference":[{"issue":"4","key":"1","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s00373-006-0666-z","article-title":"A degree constraint for uniquely Hamiltonian graphs","volume":"22","author":"Abbasi, Sarmad","year":"2006","journal-title":"Graphs Combin.","ISSN":"https:\/\/id.crossref.org\/issn\/0911-0119","issn-type":"print"},{"issue":"3","key":"2","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1002\/jgt.3190050313","article-title":"A census of maximum uniquely Hamiltonian graphs","volume":"5","author":"Barefoot, Curtiss A.","year":"1981","journal-title":"J. Graph Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0364-9024","issn-type":"print"},{"key":"3","series-title":"North-Holland Mathematical Library, Vol. 6","volume-title":"Graphs and hypergraphs","author":"Berge, Claude","year":"1973"},{"issue":"2","key":"4","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1006\/jctb.1998.1845","article-title":"Vertices of small degree in uniquely Hamiltonian graphs","volume":"74","author":"Bondy, J. A.","year":"1998","journal-title":"J. Combin. Theory Ser. B","ISSN":"https:\/\/id.crossref.org\/issn\/0095-8956","issn-type":"print"},{"issue":"3","key":"5","doi-asserted-by":"publisher","first-page":"241","DOI":"10.7155\/jgaa.00091","article-title":"On the cutting edge: simplified \ud835\udc42(\ud835\udc5b) planarity by edge addition","volume":"8","author":"Boyer, John M.","year":"2004","journal-title":"J. Graph Algorithms Appl."},{"issue":"1-2","key":"6","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/j.dam.2012.07.018","article-title":"House of Graphs: a database of interesting graphs","volume":"161","author":"Brinkmann, Gunnar","year":"2013","journal-title":"Discrete Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0166-218X","issn-type":"print"},{"issue":"2","key":"7","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1002\/jgt.22125","article-title":"Generation of cubic graphs and snarks with large girth","volume":"86","author":"Brinkmann, Gunnar","year":"2017","journal-title":"J. Graph Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0364-9024","issn-type":"print"},{"issue":"2","key":"8","first-page":"69","article-title":"Generation of cubic graphs","volume":"13","author":"Brinkmann, Gunnar","year":"2011","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"2","key":"9","first-page":"323","article-title":"Fast generation of planar graphs","volume":"58","author":"Brinkmann, Gunnar","year":"2007","journal-title":"MATCH Commun. Math. Comput. Chem.","ISSN":"https:\/\/id.crossref.org\/issn\/0340-6253","issn-type":"print"},{"key":"10","first-page":"307","article-title":"On the number of longest and almost longest cycles in cubic graphs","volume":"104","author":"Chia, Gek L.","year":"2012","journal-title":"Ars Combin.","ISSN":"https:\/\/id.crossref.org\/issn\/0381-7032","issn-type":"print"},{"key":"11","first-page":"13","article-title":"On the number of Hamilton cycles in cubic graphs","volume":"110","author":"Chia, G. L.","year":"1995","journal-title":"Congr. Numer.","ISSN":"https:\/\/id.crossref.org\/issn\/0384-9864","issn-type":"print"},{"issue":"3","key":"12","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0095-8956(80)90087-8","article-title":"Spanning cycles of nearly cubic graphs","volume":"29","author":"Entringer, R. C.","year":"1980","journal-title":"J. Combin. Theory Ser. B","ISSN":"https:\/\/id.crossref.org\/issn\/0095-8956","issn-type":"print"},{"issue":"2","key":"13","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1002\/jgt.21729","article-title":"Uniquely Hamiltonian graphs of minimum degree 4","volume":"75","author":"Fleischner, Herbert","year":"2014","journal-title":"J. Graph Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0364-9024","issn-type":"print"},{"key":"14","isbn-type":"print","volume-title":"Unique coloring of planar graphs","author":"Fowler, Thomas George","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/9780599174559"},{"key":"15","unstructured":"J. Goedgebeur, B. Meersman, and C. T. Zamfirescu, Homepage of genhypohamiltonian: \\url{http:\/\/caagt.ugent.be\/uhg\/}."},{"key":"16","unstructured":"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."},{"issue":"3","key":"17","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1002\/jgt.20205","article-title":"Independent dominating sets and Hamiltonian cycles","volume":"54","author":"Haxell, Penny","year":"2007","journal-title":"J. Graph Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0364-9024","issn-type":"print"},{"issue":"4","key":"18","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1080\/10586458.2017.1306813","article-title":"On the minimum number of Hamiltonian cycles in regular graphs","volume":"27","author":"Haythorpe, M.","year":"2018","journal-title":"Exp. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1058-6458","issn-type":"print"},{"key":"19","first-page":"111","article-title":"Planar graphs, regular graphs, bipartite graphs and Hamiltonicity","volume":"20","author":"Holton, Derek","year":"1999","journal-title":"Australas. J. Combin.","ISSN":"https:\/\/id.crossref.org\/issn\/1034-4942","issn-type":"print"},{"key":"20","unstructured":"B. D. McKay, nauty User\u2019s 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 \\url{http:\/\/cs.anu.edu.au\/ bdm\/nauty}."},{"issue":"2","key":"21","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1006\/jagm.1997.0898","article-title":"Isomorph-free exhaustive generation","volume":"26","author":"McKay, Brendan D.","year":"1998","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"key":"22","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","article-title":"Practical graph isomorphism, II","volume":"60","author":"McKay, Brendan D.","year":"2014","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"2","key":"23","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1002\/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G","article-title":"Fast generation of regular graphs and construction of cages","volume":"30","author":"Meringer, Markus","year":"1999","journal-title":"J. Graph Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0364-9024","issn-type":"print"},{"issue":"1","key":"24","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF02392606","article-title":"Die Theorie der regul\u00e4ren graphs","volume":"15","author":"Petersen, Julius","year":"1891","journal-title":"Acta Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-5962","issn-type":"print"},{"key":"25","unstructured":"I. Pivotto and G. Royle, Highly-connected planar cubic graphs with few or many Hamilton cycles, \\url{https:\/\/arxiv.org\/abs\/1901.10683}."},{"key":"26","unstructured":"G. F. Royle, The smallest uniquely hamiltonian graph with minimum degree at least 3, \\url{https:\/\/mathoverflow.net\/questions\/255784\/what-is-the-smallest-uniquely-hamiltonian-graph-with-minimum-degree-at-least-3\/}, 2017."},{"issue":"1","key":"27","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0095-8956(89)90064-6","article-title":"Enumeration of Hamiltonian cycles in certain generalized Petersen graphs","volume":"47","author":"Schwenk, Allen J.","year":"1989","journal-title":"J. Combin. Theory Ser. B","ISSN":"https:\/\/id.crossref.org\/issn\/0095-8956","issn-type":"print"},{"issue":"2","key":"28","doi-asserted-by":"publisher","first-page":"207","DOI":"10.7151\/dmgt.1784","article-title":"On uniquely Hamiltonian claw-free and triangle-free graphs","volume":"35","author":"Seamone, Ben","year":"2015","journal-title":"Discuss. Math. Graph Theory","ISSN":"https:\/\/id.crossref.org\/issn\/1234-3099","issn-type":"print"},{"key":"29","first-page":"477","article-title":"The multiplicity of Hamiltonian circuits in a graph","author":"Sheehan, John","year":"1975"},{"issue":"1","key":"30","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1002\/jgt.3190010110","article-title":"Graphs with exactly one Hamiltonian circuit","volume":"1","author":"Sheehan, John","year":"1977","journal-title":"J. Graph Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0364-9024","issn-type":"print"},{"key":"31","unstructured":"N. Sloane, The on-line encyclopedia of integer sequences, \\url{http:\/\/oeis.org\/}."},{"key":"32","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/S0167-5060(08)70511-9","article-title":"Hamiltonian cycles and uniquely edge colourable graphs","volume":"3","author":"Thomason, A. G.","year":"1978","journal-title":"Ann. Discrete Math."},{"issue":"1","key":"33","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/0095-8956(81)90089-7","article-title":"Planar cubic hypo-Hamiltonian and hypotraceable graphs","volume":"30","author":"Thomassen, Carsten","year":"1981","journal-title":"J. Combin. Theory Ser. B","ISSN":"https:\/\/id.crossref.org\/issn\/0095-8956","issn-type":"print"},{"issue":"4","key":"34","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1017\/S0963548300002182","article-title":"On the number of Hamiltonian cycles in bipartite graphs","volume":"5","author":"Thomassen, Carsten","year":"1996","journal-title":"Combin. Probab. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0963-5483","issn-type":"print"},{"issue":"1","key":"35","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1006\/jctb.1997.1794","article-title":"Independent dominating sets and a second Hamiltonian cycle in regular graphs","volume":"72","author":"Thomassen, Carsten","year":"1998","journal-title":"J. Combin. Theory Ser. B","ISSN":"https:\/\/id.crossref.org\/issn\/0095-8956","issn-type":"print"},{"key":"36","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1112\/jlms\/s1-21.2.98","article-title":"On Hamiltonian circuits","volume":"21","author":"Tutte, W. T.","year":"1946","journal-title":"J. London Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-6107","issn-type":"print"},{"key":"37","first-page":"193","article-title":"Hamiltonian circuits","author":"Tutte, William T.","year":"1976"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2020-89-322\/S0025-5718-2019-03465-8\/mcom3465_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/www.ams.org\/mcom\/2020-89-322\/S0025-5718-2019-03465-8\/S0025-5718-2019-03465-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2020-89-322\/S0025-5718-2019-03465-8\/S0025-5718-2019-03465-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T03:34:30Z","timestamp":1776828870000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2020-89-322\/S0025-5718-2019-03465-8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,5]]},"references-count":37,"journal-issue":{"issue":"322","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["S0025-5718-2019-03465-8"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3465","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2019,9,5]]}}}