{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T06:10:01Z","timestamp":1730700601539,"version":"3.28.0"},"reference-count":41,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2023,11,22]],"date-time":"2023-11-22T00:00:00Z","timestamp":1700611200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"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\/501100004497","name":"Onderzoeksraad, KU Leuven","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004497","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2024,4]]},"abstract":"Abstract<\/jats:title>In this paper, we use theoretical and computational tools to continue our investigation of \u2010hamiltonian<\/jats:italic>graphs, that is, graphs in which the removal of any pair of adjacent vertices yields a hamiltonian graph, and their interplay with \u2010hamiltonian<\/jats:italic>graphs, that is, graphs in which every vertex\u2010deleted subgraph is hamiltonian. Perhaps surprisingly, there exist graphs that are both \u2010 and \u2010hamiltonian, yet non\u2010hamiltonian, for example, the Petersen graph. Gr\u00fcnbaum conjectured that every planar \u2010hamiltonian graph must itself be hamiltonian; Thomassen disproved this conjecture. Here we show that even planar graphs that are both \u2010 and \u2010hamiltonian need not be hamiltonian, and that the number of such graphs grows at least exponentially. Motivated by results of Aldred, McKay, and Wormald, we determine for every integer that is not 14 or 17 whether there exists a \u2010hypohamiltonian<\/jats:italic>, that is non\u2010hamiltonian and \u2010hamiltonian, graph of order , and characterise all orders for which such cubic graphs and such snarks exist. We also describe the smallest cubic planar graph which is \u2010hypohamiltonian, as well as the smallest planar \u2010hypohamiltonian graph of girth 5. We conclude with open problems and by correcting two inaccuracies from the first article.<\/jats:p>","DOI":"10.1002\/jgt.23057","type":"journal-article","created":{"date-parts":[[2023,11,24]],"date-time":"2023-11-24T00:14:20Z","timestamp":1700784860000},"page":"580-611","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["K<\/i>2<\/sub>\u2010Hamiltonian graphs: II"],"prefix":"10.1002","volume":"105","author":[{"ORCID":"http:\/\/orcid.org\/0000-0001-8984-2463","authenticated-orcid":false,"given":"Jan","family":"Goedgebeur","sequence":"first","affiliation":[{"name":"Department of Computer Science KU Leuven Campus Kulak\u2010Kortrijk Kortrijk Belgium"},{"name":"Department of Applied Mathematics, Computer Science and Statistics Ghent University Ghent Belgium"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-1147-1460","authenticated-orcid":false,"given":"Jarne","family":"Renders","sequence":"additional","affiliation":[{"name":"Department of Computer Science KU Leuven Campus Kulak\u2010Kortrijk Kortrijk Belgium"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-3940-3144","authenticated-orcid":false,"given":"G\u00e1bor","family":"Wiener","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Theory, Faculty of Electrical Engineering and Informatics Budapest University of Technology and Economics Budapest Hungary"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-9673-410X","authenticated-orcid":false,"given":"Carol T.","family":"Zamfirescu","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics, Computer Science and Statistics Ghent University Ghent Belgium"},{"name":"Department of Mathematics Babe\u015f\u2010Bolyai University Cluj\u2010Napoca Romania"}]}],"member":"311","published-online":{"date-parts":[[2023,11,22]]},"reference":[{"key":"e_1_2_7_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-013-1312-1"},{"key":"e_1_2_7_3_1","first-page":"143","article-title":"Small hypohamiltonian graphs","volume":"23","author":"Aldred R. E. L.","year":"1997","journal-title":"J. Combin. Math. Combin. Comput"},{"key":"e_1_2_7_4_1","doi-asserted-by":"publisher","DOI":"10.37236\/572"},{"key":"e_1_2_7_5_1","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1972-012-3"},{"key":"e_1_2_7_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.05.001"},{"key":"e_1_2_7_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22125"},{"key":"e_1_2_7_8_1","first-page":"69","article-title":"Generation of cubic graphs","volume":"13","author":"Brinkmann G.","year":"2011","journal-title":"Discrete Math. Theor. Comput. Sci"},{"key":"e_1_2_7_9_1","first-page":"1483","article-title":"The minimality of the Georges\u2010Kelmans graph","volume":"91","author":"Brinkmann G.","year":"2022","journal-title":"Math. Comp"},{"key":"e_1_2_7_10_1","first-page":"323","article-title":"Fast generation of planar graphs","volume":"58","author":"Brinkmann G.","year":"2007","journal-title":"MATCH Commun. Math. Comput. Chem"},{"key":"e_1_2_7_11_1","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1973-008-9"},{"key":"e_1_2_7_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(77)90130-3"},{"key":"e_1_2_7_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2022.10.013"},{"key":"e_1_2_7_14_1","doi-asserted-by":"crossref","unstructured":"R.Diestel Graph theory vol. 173 Graduate Texts in Mathematics 5th ed. Springer Heidelberg 2017.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"e_1_2_7_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(74)80019-1"},{"key":"e_1_2_7_16_1","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/3465"},{"key":"e_1_2_7_17_1","doi-asserted-by":"publisher","DOI":"10.26493\/1855-3974.1044.eaa"},{"key":"e_1_2_7_18_1","doi-asserted-by":"publisher","DOI":"10.26493\/1855-3974.1176.9b7"},{"key":"e_1_2_7_19_1","unstructured":"R. L.Graham M.Gr\u00f6tschel andL.Lov\u00e1sz(eds.) Handbook of combinatorics vol.1 Elsevier 1995."},{"key":"e_1_2_7_20_1","first-page":"51","article-title":"Plane homogeneous graphs of degree three without Hamiltonian circuits","volume":"4","author":"Grinberg E. J.","year":"1968","journal-title":"Latvian Math. Yearbook, Izdat. Zinatne, Riga"},{"key":"e_1_2_7_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(74)90025-9"},{"key":"e_1_2_7_22_1","first-page":"67","article-title":"Two open problems in graph theory","volume":"22","author":"Holton D. A.","year":"1993","journal-title":"New Zealand J. Math"},{"key":"e_1_2_7_23_1","doi-asserted-by":"crossref","unstructured":"D. A.Holton andJ.Sheehan The Petersen graph Chapter 7: Hypohamiltonian graphs Cambridge University Press New York 1993.","DOI":"10.1017\/CBO9780511662058"},{"key":"e_1_2_7_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1975.11993805"},{"key":"e_1_2_7_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22015"},{"key":"e_1_2_7_26_1","unstructured":"J.Goedgebeur J.Renders G.Wiener andC. T.Zamfirescu K2\u2010Hamiltonian Graphs (Version 1) [Computer software].https:\/\/github.com\/JarneRenders\/K2-Hamiltonian-Graphs"},{"key":"e_1_2_7_27_1","first-page":"25","article-title":"Locally Hamiltonian graphs","volume":"45","author":"Katona G. O. H.","year":"1989","journal-title":"Math. Notes Acad. Sci. USSR"},{"key":"e_1_2_7_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22043"},{"key":"e_1_2_7_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"e_1_2_7_30_1","unstructured":"D. A.Nelson Hamiltonian graphs M.Sc. Thesis Vanderbilt University Nashville Tennessee USA 1973."},{"key":"e_1_2_7_31_1","doi-asserted-by":"crossref","unstructured":"K.Ozeki Personal communication May2019.","DOI":"10.1299\/jsmemecj.2019.J18103"},{"key":"e_1_2_7_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199601)21:1<43::AID-JGT6>3.0.CO;2-M"},{"key":"e_1_2_7_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1058"},{"key":"e_1_2_7_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70511-9"},{"key":"e_1_2_7_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90071-6"},{"key":"e_1_2_7_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0070410"},{"key":"e_1_2_7_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(81)90089-7"},{"key":"e_1_2_7_38_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1956-0081471-8"},{"key":"e_1_2_7_39_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22173"},{"key":"e_1_2_7_40_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20513"},{"key":"e_1_2_7_41_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21815"},{"key":"e_1_2_7_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1355252"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.23057","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,3]],"date-time":"2024-11-03T04:37:50Z","timestamp":1730608670000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.23057"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,22]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["10.1002\/jgt.23057"],"URL":"https:\/\/doi.org\/10.1002\/jgt.23057","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"type":"print","value":"0364-9024"},{"type":"electronic","value":"1097-0118"}],"subject":[],"published":{"date-parts":[[2023,11,22]]},"assertion":[{"value":"2022-08-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}