{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T07:04:16Z","timestamp":1770966256813,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T00:00:00Z","timestamp":1764806400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T00:00:00Z","timestamp":1764806400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000086","name":"Directorate for Mathematical and Physical Sciences","doi-asserted-by":"publisher","award":["1855165"],"award-info":[{"award-number":["1855165"]}],"id":[{"id":"10.13039\/100000086","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2026,2]]},"abstract":"Abstract<\/jats:title>\n \n For\n \n \n $$d \\ge 2$$<\/jats:tex-math>\n \n \n d<\/mml:mi>\n \u2265<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , we show that all graphs of\n d<\/jats:italic>\n -polytopes have a Hamiltonian line graph if and only if\n \n \n $$d \\ne 3$$<\/jats:tex-math>\n \n \n d<\/mml:mi>\n \u2260<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n : We exhibit a graph of a 3-polytope on 252 vertices whose line graph does not even have Hamiltonian paths. Adapting a construction by Gr\u00fcnbaum and Motzkin, for large\n n<\/jats:italic>\n we also construct simple 3-polytopes on 3\n n<\/jats:italic>\n vertices in whose line graph any simple path is shorter than\n \n \n $$10 n^{\\alpha }$$<\/jats:tex-math>\n \n \n 10<\/mml:mn>\n \n n<\/mml:mi>\n \u03b1<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , for some constant\n \n \n $$\\alpha <1$$<\/jats:tex-math>\n \n \n \u03b1<\/mml:mi>\n <<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Moreover, we give four elementary counterexamples of plausible extensions to simplicial complexes of four famous results in Hamiltonian graph theory.\n <\/jats:p>","DOI":"10.1007\/s00373-025-02988-5","type":"journal-article","created":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T20:09:24Z","timestamp":1764878964000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Higher-dimensional counterexamples to Hamiltonicity"],"prefix":"10.1007","volume":"42","author":[{"given":"Bruno","family":"Benedetti","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0007-0827-4291","authenticated-orcid":false,"given":"Marta","family":"Pavelka","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,12,4]]},"reference":[{"issue":"1","key":"2988_CR1","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s11512-009-0106-4","volume":"49","author":"CA Athanasiadis","year":"2011","unstructured":"Athanasiadis, C.A.: Some combinatorial properties of flag simplicial pseudomanifolds and spheres. Ark. Mat. 49(1), 17\u201329 (2011)","journal-title":"Ark. Mat."},{"key":"2988_CR2","first-page":"347","volume":"1969","author":"D Barnette","year":"1968","unstructured":"Barnette, D.: Conjecture 5. Proceedings of the Third Waterloo Conference on Combinatorics 1969, 347 (1968)","journal-title":"Proceedings of the Third Waterloo Conference on Combinatorics"},{"key":"2988_CR3","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/BF02771721","volume":"41","author":"D Barnette","year":"1982","unstructured":"Barnette, D.: Decompositions of homology manifolds and their graphs. Israel J. Math. 41, 203\u2013212 (1982)","journal-title":"Israel J. Math."},{"key":"2988_CR4","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/BF02761971","volume":"16","author":"D Barnette","year":"1973","unstructured":"Barnette, D.: Graph theorems for manifolds. Israel J. Math. 16, 62\u201372 (1973)","journal-title":"Israel J. Math."},{"key":"2988_CR5","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0021-9800(70)80019-9","volume":"9","author":"LW Beineke","year":"1970","unstructured":"Beineke, L.W.: Characterization of Derived Graphs. Journal of Combinatorial theory 9, 129\u2013135 (1970)","journal-title":"Journal of Combinatorial theory"},{"key":"2988_CR6","doi-asserted-by":"publisher","first-page":"P102407","DOI":"10.1016\/j.aam.2022.102407","volume":"141","author":"B Benedetti","year":"2022","unstructured":"Benedetti, B., Seccia, L., Varbaro, M.: Hamiltonian paths, unit-interval complexes, and determinantal facet ideals. Adv. Appl. Math. 141, P102407 (2022)","journal-title":"Adv. Appl. Math."},{"issue":"17","key":"2988_CR7","doi-asserted-by":"publisher","first-page":"8085","DOI":"10.1093\/imrn\/rnu191","volume":"2015","author":"B Benedetti","year":"2015","unstructured":"Benedetti, B., Varbaro, M.: On the Dual Graphs of Cohen-Macaulay Algebras. Int. Math. Res. Not. 2015(17), 8085\u20138115 (2015)","journal-title":"Int. Math. Res. Not."},{"key":"2988_CR8","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0020-0190(83)90078-9","volume":"17","author":"AA Bertossi","year":"1983","unstructured":"Bertossi, A.A.: Finding Hamiltonian circuits in proper interval graphs. Inf. Process. Lett. 17, 97\u2013101 (1983)","journal-title":"Inf. Process. Lett."},{"key":"2988_CR9","doi-asserted-by":"publisher","first-page":"4123","DOI":"10.1090\/proc\/12415","volume":"143","author":"A Bj\u00f6rner","year":"2015","unstructured":"Bj\u00f6rner, A., Vorwerk, K.: On the Connectivity of Manifold Graphs. Proceedings of the American Mathematical Society 143, 4123\u20134132 (2015)","journal-title":"Proceedings of the American Mathematical Society"},{"key":"2988_CR10","unstructured":"Brinkmann, G., McKay, B.: Combinatorial Data, Plane Graphs, available at http:\/\/users.cecs.anu.edu.au\/~bdm\/data\/planegraphs.html"},{"key":"2988_CR11","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s00373-011-1090-6","volume":"28","author":"HJ Broersma","year":"2012","unstructured":"Broersma, H.J., Ryj\u00e1\u010dek, Z., Vr\u00e1na, P.: How Many Conjectures Can You Stand? A Survey, Graphs and Combinatorics 28, 57\u201375 (2012)","journal-title":"A Survey, Graphs and Combinatorics"},{"key":"2988_CR12","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1090\/S0002-9947-1968-0231740-1","volume":"134","author":"G Chartrand","year":"1968","unstructured":"Chartrand, G.: On Hamiltonian line graphs, Transaction of the. American Mathematical Society 134, 559\u2013566 (1968)","journal-title":"American Mathematical Society"},{"key":"2988_CR13","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/S0012-365X(96)00307-X","volume":"170","author":"C Chen","year":"1997","unstructured":"Chen, C., Chang, C.C., Chang, G.J.: Proper interval graphs and the guard problem. Discret. Math. 170, 223\u2013230 (1997)","journal-title":"Discret. Math."},{"key":"2988_CR14","unstructured":"Chen, Z., Lai, H., Lai, H., Weng, G.: Jackson\u2019s conjecture on Eulerian subgraphs, Combinatorics, graph theory, algorithms, and applications in Beijing, 53\u201358 (1993)"},{"issue":"B","key":"2988_CR15","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0095-8956(72)90020-2","volume":"12","author":"V Chv\u00e1tal","year":"1972","unstructured":"Chv\u00e1tal, V.: On Hamilton\u2019s Ideals. Journal of combinatorial theory 12(B), 163\u2013168 (1972)","journal-title":"Journal of combinatorial theory"},{"key":"2988_CR16","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF02023582","volume":"14","author":"L Clark","year":"1983","unstructured":"Clark, L., Entringer, R.: Smallest maximally non-Hamiltonian graphs. Period. Math. Hung. 14, 57\u201368 (1983)","journal-title":"Period. Math. Hung."},{"key":"2988_CR17","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/BF02349959","volume":"8","author":"L Clark","year":"1992","unstructured":"Clark, L., Entringer, R., Shapiro, H.D.: Smallest maximally non-Hamiltonian graphs II. Graphs and Combinatorics 8, 225\u2013231 (1992)","journal-title":"Graphs and Combinatorics"},{"issue":"1","key":"2988_CR18","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1112\/plms\/s3-2.1.69","volume":"3","author":"GA Dirac","year":"1952","unstructured":"Dirac, G.A.: Some theorems on abstract graphs. Proceedings of the London Mathematical Society 3(1), 69\u201381 (1952)","journal-title":"Proceedings of the London Mathematical Society"},{"issue":"B","key":"2988_CR19","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0095-8956(74)90091-4","volume":"16","author":"H Fleischner","year":"1974","unstructured":"Fleischner, H.: The square of every two-connected graph is Hamiltonian. Journal of Combinatorial Theory, Series 16(B), 29\u201334 (1974)","journal-title":"Journal of Combinatorial Theory, Series"},{"key":"2988_CR20","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1112\/jlms\/s1-37.1.152","volume":"37","author":"B Gr\u00fcnbaum","year":"1962","unstructured":"Gr\u00fcnbaum, B., Motzkin, T.S.: Longest simple paths in polyhedral graphs. J. Lond. Math. Soc. 37, 152\u2013160 (1962)","journal-title":"J. Lond. Math. Soc."},{"key":"2988_CR21","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/j.jctb.2009.10.002","volume":"100","author":"H H\u00e1n","year":"2010","unstructured":"H\u00e1n, H., Schacht, M.: Dirac-type results for loose Hamilton cycles in uniform hypergraphs. Journal of Combinatorial Theory B 100, 332\u2013346 (2010)","journal-title":"Journal of Combinatorial Theory B"},{"key":"2988_CR22","doi-asserted-by":"publisher","first-page":"701","DOI":"10.4153\/CMB-1965-051-3","volume":"8","author":"F Harary","year":"1965","unstructured":"Harary, F., St, C.: John Alva Nash-Williams, On Eulerian and Hamiltonian graphs and line graphs. Can. Math. Bull. 8, 701\u2013709 (1965)","journal-title":"Can. Math. Bull."},{"key":"2988_CR23","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1016\/j.ejc.2011.09.015","volume":"33","author":"T Kaiser","year":"2012","unstructured":"Kaiser, T., Vr\u00e1na, P.: Hamilton cycles in 5-connected line graphs. Eur. J. Comb. 33, 924\u2013947 (2012)","journal-title":"Eur. J. Comb."},{"key":"2988_CR24","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility Among Combinatorial Problems, Complexity of Computer Computations, 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"2988_CR25","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/(SICI)1097-0118(199903)30:3<205::AID-JGT5>3.0.CO;2-O","volume":"30","author":"GY Katona","year":"1999","unstructured":"Katona, G.Y., Kierstead, H.A.: Hamiltonian chains in hypergraphs. Journal of Graph Theory 30, 205\u2013212 (1999)","journal-title":"Journal of Graph Theory"},{"key":"2988_CR26","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1016\/j.disc.2010.11.013","volume":"311","author":"P Keevash","year":"2011","unstructured":"Keevash, P., K\u00fchn, D., Mycroft, R., Osthus, D.: Loose Hamilton cycles in hypergraphs. Discret. Math. 311, 544\u2013559 (2011)","journal-title":"Discret. Math."},{"key":"2988_CR27","first-page":"81","volume":"1","author":"V Klee","year":"1975","unstructured":"Klee, V.: A d-pseudomanifold with $$f_0$$ vertices has at least d$$f_0-(d-1)(d+2)$$$$d$$-simplices. Houst. J. Math. 1, 81\u201386 (1975)","journal-title":"Houst. J. Math."},{"key":"2988_CR28","first-page":"77","volume":"21","author":"H Kronk","year":"1969","unstructured":"Kronk, H.: A generalization of a theorem of P\u00f3sa. Proceedings of the American Mathematical Society 21, 77\u201378 (1969)","journal-title":"Proceedings of the American Mathematical Society"},{"key":"2988_CR29","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1016\/j.jctb.2006.02.004","volume":"96","author":"D K\u00fchn","year":"2006","unstructured":"K\u00fchn, D., Osthus, D.: Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree. Journal of Combinatorial Theory, Series B 96, 767\u2013821 (2006)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"2988_CR30","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/j.jctb.2022.02.008","volume":"155","author":"X Liu","year":"2022","unstructured":"Liu, X., Wang, Z., Yu, X.: Counting Hamiltonian cycles in planar triangulations. Journal of Combinatorial Theory, Series B 155, 256\u2013277 (2022)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"2988_CR31","unstructured":"Mohar, B.: Hamiltonicity of graphs of convex polytopes (2001). https:\/\/users.fmf.uni-lj.si\/mohar\/Problems\/P10HamiltonicityPolytopes.html"},{"key":"2988_CR32","doi-asserted-by":"publisher","first-page":"629","DOI":"10.2140\/pjm.1963.13.629","volume":"13","author":"JW Moon","year":"1963","unstructured":"Moon, J.W., Moser, L.: Simple paths on polyhedra. Pac. J. Math. 13, 629\u2013631 (1963)","journal-title":"Pac. J. Math."},{"key":"2988_CR33","unstructured":"Pavelka, M.: A software for detecting closure properties in simplicial complexes, available at (2021). https:\/\/detector.martapavelka.com\/"},{"key":"2988_CR34","unstructured":"Pavelka, M.: Planar graphs check for line-Hamiltonicity, available at (2023). https:\/\/github.com\/martapavelka\/scsc\/blob\/master\/PlanarGraphCheck.ipynb"},{"key":"2988_CR35","unstructured":"Pietro, G., Rip\u00e0, M.: On the existence of Hamiltonian cycles in hypercubes (2024). arXiv:2409.03073"},{"key":"2988_CR36","first-page":"225","volume":"7","author":"L P\u00f3sa","year":"1962","unstructured":"P\u00f3sa, L.: A theorem concerning Hamilton lines, Magyar Tudom\u00e1nyos Akad\u00e9mia. Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei 7, 225\u2013226 (1962)","journal-title":"Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei"},{"key":"2988_CR37","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s00493-008-2295-z","volume":"28","author":"V Rodl","year":"2008","unstructured":"Rodl, V., Szemer\u00e9di, E., Ruci\u0144ski, A.: An approximate Dirac-type theorem for k-uniform hypergraphs. Combinatorica 28, 229\u2013260 (2008)","journal-title":"Combinatorica"},{"key":"2988_CR38","first-page":"277","volume":"13","author":"PV Roldugin","year":"2003","unstructured":"Roldugin, P.V.: Construction of maximally non-Hamiltonian graphs. Discrete Mathematics, Algorithms and Applications 13, 277\u2013289 (2003)","journal-title":"Discrete Mathematics, Algorithms and Applications"},{"key":"2988_CR39","unstructured":"SageMath: the Sage Mathematics Software System. https:\/\/www.sagemath.org"},{"key":"2988_CR40","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1017\/S0370164600044229","volume":"10","author":"PG Tait","year":"1880","unstructured":"Tait, P.G.: Remarks on the coloring of maps. Proc. R. Soc. Edinb. 10, 501\u2013503 (1880)","journal-title":"Proc. R. Soc. Edinb."},{"key":"2988_CR41","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1112\/jlms\/s1-21.2.98","volume":"21","author":"WT Tutte","year":"1946","unstructured":"Tutte, W.T.: On Hamiltonian circuits. J. Lond. Math. Soc. 21, 98\u2013101 (1946)","journal-title":"J. Lond. Math. Soc."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02988-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-025-02988-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02988-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T06:05:06Z","timestamp":1770962706000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-025-02988-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["2988"],"URL":"https:\/\/doi.org\/10.1007\/s00373-025-02988-5","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]},"assertion":[{"value":"30 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 October 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 December 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"3"}}