{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T23:35:27Z","timestamp":1780097727902,"version":"3.54.0"},"reference-count":25,"publisher":"American Mathematical Society (AMS)","issue":"335","license":[{"start":{"date-parts":[[2022,11,17]],"date-time":"2022-11-17T00:00:00Z","timestamp":1668643200000},"content-version":"am","delay-in-days":365,"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"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    In 1971, Tutte wrote in an article that\n                    <italic>it is tempting to conjecture that every 3-connected bipartite cubic graph is hamiltonian<\/italic>\n                    . Motivated by this remark, Horton constructed a counterexample on\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"96\">\n                        <mml:semantics>\n                          <mml:mn>96<\/mml:mn>\n                          <mml:annotation encoding=\"application\/x-tex\">96<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    vertices. In a sequence of articles by different authors several smaller counterexamples were presented. The smallest of these graphs is a graph on 50 vertices which was discovered independently by Georges and Kelmans. In this article we show that there is no smaller counterexample. As all non-hamiltonian 3-connected bipartite cubic graphs in the literature have cyclic 4-cuts\u2014even if they have girth 6\u2014it is natural to ask whether this is a necessary prerequisite. In this article we answer this question in the negative and give a construction of an infinite family of non-hamiltonian cyclically 5-connected bipartite cubic graphs.\n                  <\/p>\n                  <p>In 1969 Barnette gave a weaker version of the conjecture stating that 3-connected planar bipartite cubic graphs are hamiltonian. We show that Barnette\u2019s conjecture is true up to at least 90 vertices. We also report that a search of small non-hamiltonian 3-connected bipartite cubic graphs did not find any with genus less than\u00a04.<\/p>","DOI":"10.1090\/mcom\/3701","type":"journal-article","created":{"date-parts":[[2021,10,6]],"date-time":"2021-10-06T09:53:43Z","timestamp":1633514023000},"page":"1483-1500","source":"Crossref","is-referenced-by-count":2,"title":["The minimality of the Georges\u2013Kelmans graph"],"prefix":"10.1090","volume":"91","author":[{"given":"Gunnar","family":"Brinkmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Goedgebeur","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Brendan","family":"McKay","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"14","published-online":{"date-parts":[[2021,11,17]]},"reference":[{"key":"1","unstructured":"R. E. L. Aldred, G. Brinkmann, and B. D. McKay, Announcement about Barnette\u2019s conjecture, 2000, \\url{https:\/\/www.fmf.uni-lj.si\/ mohar\/Problems\/P4BarnetteConjecture.html}."},{"key":"2","unstructured":"D. Barnette, Conjecture 5. Recent progress in combinatorics, Proceedings of the Third Waterloo Conference on Combinatorics, Academic Press, New York, 1969."},{"key":"3","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph theory with applications","author":"Bondy, J. A.","year":"1976"},{"issue":"2","key":"4","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1002\/(SICI)1097-0118(199610)23:2<139::AID-JGT5>3.3.CO;2-1","article-title":"Fast generation of cubic graphs","volume":"23","author":"Brinkmann, Gunnar","year":"1996","journal-title":"J. Graph Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0364-9024","issn-type":"print"},{"key":"5","unstructured":"G. Brinkmann, A practical algorithm for the computation of the genus, preprint arXiv:2005.08243, 2020."},{"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"},{"key":"7","unstructured":"G. Brinkmann, J. Goedgebeur, and B. D. McKay, Software archive for cubic bipartite non-hamiltonian graphs, 2021, \\url{https:\/\/caagt.ugent.be\/cubic-bip-nonham}."},{"issue":"2","key":"8","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":"9","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph theory","volume":"173","author":"Diestel, Reinhard","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642142789","edition":"4"},{"key":"10","unstructured":"M. N. Ellingham, Cycles in 3-connected cubic graphs, Master\u2019s thesis, University of Melbourne, 1982."},{"issue":"3","key":"11","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1016\/0095-8956(83)90046-1","article-title":"Non-Hamiltonian 3-connected cubic bipartite graphs","volume":"34","author":"Ellingham, M. N.","year":"1983","journal-title":"J. Combin. Theory Ser. B","ISSN":"https:\/\/id.crossref.org\/issn\/0095-8956","issn-type":"print"},{"issue":"1","key":"12","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0095-8956(89)90012-9","article-title":"Non-Hamiltonian bicubic graphs","volume":"46","author":"Georges, John P.","year":"1989","journal-title":"J. Combin. Theory Ser. B","ISSN":"https:\/\/id.crossref.org\/issn\/0095-8956","issn-type":"print"},{"issue":"44","key":"13","first-page":"73","article-title":"Konstruktion schlichter Graphen mit gegebener Gradpartition","author":"Grund, Roland","year":"1993","journal-title":"Bayreuth. Math. Schr.","ISSN":"https:\/\/id.crossref.org\/issn\/0172-1062","issn-type":"print"},{"issue":"3","key":"14","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/0095-8956(85)90072-3","article-title":"Hamiltonian cycles in cubic 3-connected bipartite planar graphs","volume":"38","author":"Holton, D. A.","year":"1985","journal-title":"J. Combin. Theory Ser. B","ISSN":"https:\/\/id.crossref.org\/issn\/0095-8956","issn-type":"print"},{"issue":"3","key":"15","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0095-8956(88)90075-5","article-title":"The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices","volume":"45","author":"Holton, D. A.","year":"1988","journal-title":"J. Combin. Theory Ser. B","ISSN":"https:\/\/id.crossref.org\/issn\/0095-8956","issn-type":"print"},{"issue":"1","key":"16","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0012-365X(82)90079-6","article-title":"On two-factors of bipartite regular graphs","volume":"41","author":"Horton, J. D.","year":"1982","journal-title":"Discrete Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-365X","issn-type":"print"},{"issue":"3","key":"17","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1070\/RM1988v043n03ABEH001738","article-title":"Cubic bipartite cyclically 4-connected graphs with no Hamiltonian cycles","volume":"43","author":"Kelmans, A. K.","year":"1988","journal-title":"Uspekhi Mat. Nauk","ISSN":"https:\/\/id.crossref.org\/issn\/0042-1316","issn-type":"print"},{"key":"18","series-title":"American Mathematical Society Translations, Series 2","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1090\/trans2\/158","volume-title":"Selected topics in discrete mathematics","volume":"158","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0821875094"},{"key":"19","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.ejc.2018.09.004","article-title":"Cuts in matchings of 3-connected cubic graphs","volume":"76","author":"Knauer, Kolja","year":"2019","journal-title":"European J. Combin.","ISSN":"https:\/\/id.crossref.org\/issn\/0195-6698","issn-type":"print"},{"issue":"1","key":"20","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/0095-8956(92)90004-H","article-title":"Edge reductions in cyclically \ud835\udc58-connected cubic graphs","volume":"56","author":"McCuaig, William","year":"1992","journal-title":"J. Combin. Theory Ser. B","ISSN":"https:\/\/id.crossref.org\/issn\/0095-8956","issn-type":"print"},{"key":"21","doi-asserted-by":"crossref","unstructured":"B. D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014), 94\u2013112, The latest version of the software is available at \\url{http:\/\/users.cecs.anu.edu.au\/ bdm\/nauty\/}.","DOI":"10.1016\/j.jsc.2013.09.003"},{"issue":"2","key":"22","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"},{"key":"23","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"},{"issue":"2","key":"24","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0012-365X(71)90027-6","article-title":"On the 2-factors of bicubic graphs","volume":"1","author":"Tutte, W. T.","year":"1971","journal-title":"Discrete Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-365X","issn-type":"print"},{"key":"25","isbn-type":"print","first-page":"239","article-title":"Models of random regular graphs","author":"Wormald, N. C.","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/0521653762"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2022-91-335\/S0025-5718-2021-03701-1\/mcom3701_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/www.ams.org\/mcom\/2022-91-335\/S0025-5718-2021-03701-1\/S0025-5718-2021-03701-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T04:29:48Z","timestamp":1776832188000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2022-91-335\/S0025-5718-2021-03701-1\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,17]]},"references-count":25,"journal-issue":{"issue":"335","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["S0025-5718-2021-03701-1"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3701","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":[[2021,11,17]]}}}