{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T07:03:53Z","timestamp":1770966233491,"version":"3.50.1"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T00:00:00Z","timestamp":1765843200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T00:00:00Z","timestamp":1765843200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"ARIS","award":["BI-ME\/23-24-022"],"award-info":[{"award-number":["BI-ME\/23-24-022"]}]},{"name":"ARIS","award":["P1-0297"],"award-info":[{"award-number":["P1-0297"]}]},{"name":"ARIS","award":["N1-0218"],"award-info":[{"award-number":["N1-0218"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2026,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    A path factor in a graph\n                    <jats:italic>G<\/jats:italic>\n                    is a factor of\n                    <jats:italic>G<\/jats:italic>\n                    in which every component is a path on at least two vertices. Let\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$T\\Box P_n$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>T<\/mml:mi>\n                            <mml:mo>\u25a1<\/mml:mo>\n                            <mml:msub>\n                              <mml:mi>P<\/mml:mi>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:msub>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    be the Cartesian product of a tree\n                    <jats:italic>T<\/jats:italic>\n                    and a path on\n                    <jats:italic>n<\/jats:italic>\n                    vertices. Kao and Weng [11] proved that\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$T\\Box P_n$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>T<\/mml:mi>\n                            <mml:mo>\u25a1<\/mml:mo>\n                            <mml:msub>\n                              <mml:mi>P<\/mml:mi>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:msub>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is hamiltonian if\n                    <jats:italic>T<\/jats:italic>\n                    has a path factor,\n                    <jats:italic>n<\/jats:italic>\n                    is an even integer and\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$n\\ge 4\\Delta (T)-2$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>\u2265<\/mml:mo>\n                            <mml:mn>4<\/mml:mn>\n                            <mml:mi>\u0394<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>T<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                            <mml:mo>-<\/mml:mo>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . They conjectured that for every\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\Delta \\ge 3$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>\u0394<\/mml:mi>\n                            <mml:mo>\u2265<\/mml:mo>\n                            <mml:mn>3<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    there exists a connected graph\n                    <jats:italic>G<\/jats:italic>\n                    of maximum degree\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\Delta $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u0394<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    which has a path factor, such that for every even\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$n&lt; 4\\Delta -2$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>&lt;<\/mml:mo>\n                            <mml:mn>4<\/mml:mn>\n                            <mml:mi>\u0394<\/mml:mi>\n                            <mml:mo>-<\/mml:mo>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    the product\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$G\\Box P_n$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>G<\/mml:mi>\n                            <mml:mo>\u25a1<\/mml:mo>\n                            <mml:msub>\n                              <mml:mi>P<\/mml:mi>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:msub>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is not hamiltonian. In this article we prove this conjecture.\n                  <\/jats:p>","DOI":"10.1007\/s00373-025-03005-5","type":"journal-article","created":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T18:47:14Z","timestamp":1765910834000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Hamiltonicity of Cartesian products of graphs"],"prefix":"10.1007","volume":"42","author":[{"given":"Irena Hrastnik","family":"Ladinek","sequence":"first","affiliation":[]},{"given":"\u1e90ana Kovijani\u0107","family":"Vuki\u0107evi\u0107","sequence":"additional","affiliation":[]},{"given":"Tja\u0161a Paj","family":"Erker","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2175-4218","authenticated-orcid":false,"given":"Simon","family":"\u0160pacapan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,12,16]]},"reference":[{"key":"3005_CR1","first-page":"97","volume":"16","author":"J Akiyama","year":"1980","unstructured":"Akiyama, J., Avis, D., Era, H.: On a {1,2}-factor of a graph. TRU Math. 16, 97\u2013102 (1980)","journal-title":"TRU Math."},{"key":"3005_CR2","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0012-365X(82)90297-7","volume":"38","author":"V Batagelj","year":"1982","unstructured":"Batagelj, V., Pisanski, T.: Hamiltonian cycles in the Cartesian product of a tree and a cycle. Discrete Math. 38, 311\u2013312 (1982)","journal-title":"Discrete Math."},{"key":"3005_CR3","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/S0166-218X(99)00141-9","volume":"99","author":"D Bauer","year":"2000","unstructured":"Bauer, D., Broersma, H.J., Veldman, H.J.: Not every $$2$$-tough graph is Hamiltonian. Discrete Appl. Math. 99, 317\u2013321 (2000)","journal-title":"Discrete Appl. Math."},{"key":"3005_CR4","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0012-365X(73)90138-6","volume":"5","author":"V Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal, V.: Tough graphs and Hamiltonian circuits. Discrete Math. 5, 215\u2013228 (1973)","journal-title":"Discrete Math."},{"key":"3005_CR5","doi-asserted-by":"publisher","first-page":"6337","DOI":"10.1016\/j.disc.2008.11.024","volume":"309","author":"R \u0106ada","year":"2009","unstructured":"\u0106ada, R., Flandrin, E., Li, H.: Hamiltonicity and pancyclicity of cartesian products of graphs. Discrete Math. 309, 6337\u20136343 (2009)","journal-title":"Discrete Math."},{"key":"3005_CR6","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.ipl.2005.05.016","volume":"96","author":"V Dimakopoulos","year":"2005","unstructured":"Dimakopoulos, V., Palios, L., Poulakidas, A.: On the Hamiltonicity of the Cartesian product. Inform. Process. Lett. 96, 49\u201353 (2005)","journal-title":"Inform. Process. Lett."},{"key":"3005_CR7","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1007\/s00026-021-00548-1","volume":"25","author":"JB Gauci","year":"2021","unstructured":"Gauci, J.B., Zerafa, J.P.: Perfect matchings and hamiltonicity in the Cartesian product of cycles. Ann. Comb. 25, 789\u2013796 (2021)","journal-title":"Ann. Comb."},{"key":"3005_CR8","unstructured":"Hrastnik Ladinek, I., Kovijani\u0107 Vuki\u0107evi\u0107, \u017d., Paj Erker, T., \u0160pacapan, S.: Hamiltonicity of Cartesian products of graphs. arXiv:2408.06770"},{"key":"3005_CR9","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1002\/jgt.20250","volume":"56","author":"T Kaiser","year":"2007","unstructured":"Kaiser, T., Kr\u00e1l\u2019, D., Rosenfeld, M., Ryj\u00e1\u010dek, Z., Voss, H.-J.: Hamilton cycles in prisms. J. Graph Theory 56, 249\u2013269 (2007)","journal-title":"J. Graph Theory"},{"key":"3005_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00373-013-1377-x","volume":"30","author":"RJ Gould","year":"2014","unstructured":"Gould, R.J.: Recent Advances on the Hamiltonian Problem: survey III. Graphs Combin. 30, 1\u201346 (2014)","journal-title":"Graphs Combin."},{"key":"3005_CR11","doi-asserted-by":"publisher","first-page":"933","DOI":"10.1007\/s00373-021-02292-y","volume":"37","author":"L Kao","year":"2021","unstructured":"Kao, L., Weng, C.: The relation between Hamiltonian and $$1$$-tough properties of the Cartesian product graphs. Graphs Combin. 37, 933\u2013943 (2021)","journal-title":"Graphs Combin."},{"key":"3005_CR12","first-page":"143","volume":"126","author":"WD Wallis","year":"1988","unstructured":"Wallis, W.D., Wang, Z.: Hamilton cycles in Cartesian products, Combinatorial designs and applications. Lecture Notes Pure Appl. Math. 126, 143\u2013158 (1988)","journal-title":"Lecture Notes Pure Appl. Math."},{"key":"3005_CR13","doi-asserted-by":"crossref","unstructured":"Zaks, J.: Hamiltonian cycles in products of graphs. Canad. Math. Bull. 17, 763\u2013765 (1974\/75)","DOI":"10.4153\/CMB-1974-138-7"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-03005-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-025-03005-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-03005-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T06:04:53Z","timestamp":1770962693000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-025-03005-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,16]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["3005"],"URL":"https:\/\/doi.org\/10.1007\/s00373-025-03005-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,16]]},"assertion":[{"value":"26 August 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 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 declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}],"article-number":"7"}}