{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:45:13Z","timestamp":1787323513556,"version":"build-2736575974"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","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":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>Motivated by a conjecture of Gr\u00fcnbaum and a problem of Katona, Kostochka, Pach, and Stechkin, both dealing with non-Hamiltonian $n$-vertex graphs and their $(n-2)$-cycles, we investigate $K_2$- Hamiltonian graphs, i.e., graphs in which the removal of any pair of adjacent vertices yields a Hamiltonian graph. In this first part, we prove structural properties and show that there exist infinitely many cubic non-Hamiltonian $K_2$-Hamiltonian graphs, both of the 3-edge-colorable and the non-3-edge-colorable variety. In fact, cubic $K_2$-Hamiltonian graphs with chromatic index 4 (such as Petersen's graph) are a subset of the critical snarks. On the other hand, it is proven that non-Hamiltonian $K_2$-Hamiltonian graphs of any maximum degree exist. Several operations conserving $K_2$-Hamiltonicity are described, one of which leads to the result that there exists an infinite family of non-Hamiltonian $K_2$-Hamiltonian graphs in which, asymptotically, a quarter of vertices has the property that removing such a vertex yields a non-Hamiltonian graph. We extend a celebrated result of Tutte by showing that every planar $K_2$-Hamiltonian graph with minimum degree at least 4 is Hamiltonian. Finally, we investigate $K_2$-traceable graphs and discuss open problems.<\/jats:p>","DOI":"10.1137\/20m1355252","type":"journal-article","created":{"date-parts":[[2021,7,29]],"date-time":"2021-07-29T10:43:53Z","timestamp":1627555433000},"page":"1706-1728","source":"Crossref","is-referenced-by-count":4,"title":["$K_2$-Hamiltonian Graphs: I"],"prefix":"10.1137","volume":"35","author":[{"given":"Carol T.","family":"Zamfirescu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,7,29]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-013-1312-1"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1972-012-3"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1998.1845"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.37236\/7771"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1972.40.53"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2019.111717"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1973-008-9"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02023582"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1950-09407-5"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , 5th ed., Grad. Texts in Math. 173, Springer, New York, 2016.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-11910"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(74)80019-1"},{"key":"atypb13","unstructured":"T. Gallai,\n                      Theory of Graphs\n                      , Proc. Colloq. Tihany, P. Erd\u00f6s and G. Katona, eds., 1966, Academic Press, New York, 1968."},{"key":"atypb14","unstructured":"J. Goedgebeur,\n                      private communication\n                      , 2020."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22183"},{"key":"atypb17","unstructured":"R. L. Graham, M. Gr\u00f6tschel, and L. Lov\u00e1sz, eds.\n                      Handbook of Combinatorics\n                      , Vol. 1. Elsevier, Amsterdam, 1995."},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"B. Gr\u00fcnbaum,\n                      Vertices Missed by Longest Paths or Circuits\n                      , J. Combin. Theory Ser. A, 17 (1974), pp. 31-38.","DOI":"10.1016\/0097-3165(74)90025-9"},{"key":"atypb19","first-page":"432","volume":"63","author":"Gutt S.","year":"1977","journal-title":"Acad. Roy. Belg. Bull. Cl. Sci. V. S\u00e9r."},{"key":"atypb20","first-page":"214","author":"Holton D. A.","year":"1993","journal-title":"New York"},{"key":"atypb21","unstructured":"J. D. Horton,\n                      A Hypotraceable Graph\n                      , Research Report CORR 73-4, Department of Combinatorics and Optimization, University of Waterloo, 1973."},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"L.H. Hsu and C.K. Lin,\n                      Graph Theory and Interconnection Networks\n                      , CRC Press, Boca Raton, FL, 2008.","DOI":"10.1201\/9781420044829"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1975.11993805"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22015"},{"key":"atypb25","first-page":"25","volume":"45","author":"Katona G. O. H.","year":"1989","journal-title":"Math. Notes Acad. Sci. USSR"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.37236\/8440"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199607)22:3<253::AID-JGT6>3.0.CO;2-L"},{"key":"atypb28","unstructured":"D. A. Nelson,\n                      Hamiltonian Graphs\n                      , M.Sc. thesis, Vanderbilt University, Nashville, TN, 1973."},{"key":"atypb29","unstructured":"G. N. Robertson,\n                      Graphs Minimal Under Girth, Valency and Connectivity Constraints\n                      , Ph.D. thesis, University of Waterloo, 1969."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199601)21:1<43::AID-JGT6>3.0.CO;2-M"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199704)24:4<341::AID-JGT6>3.0.CO;2-O"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1058"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90074-0"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90071-6"},{"key":"atypb35","first-page":"557","author":"Thomassen C.","year":"1978","journal-title":"Berlin"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(81)90089-7"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1956-0081471-8"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(69)80098-0"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22034"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22173"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.02.017"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21815"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-11630"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1355252","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:06:50Z","timestamp":1787321210000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1355252"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1355252"],"URL":"https:\/\/doi.org\/10.1137\/20m1355252","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}