{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T01:14:04Z","timestamp":1777511644743,"version":"3.51.4"},"reference-count":36,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2024,4,17]],"date-time":"2024-04-17T00:00:00Z","timestamp":1713312000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2024,9]]},"abstract":"Abstract<\/jats:title>The bipartite independence number<\/jats:italic> of a graph \n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, denoted as \n$\\tilde \\alpha (G)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, is the minimal number \n$k$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> such that there exist positive integers \n$a$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and \n$b$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with \n$a+b=k+1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with the property that for any two disjoint sets \n$A,B\\subseteq V(G)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with \n$|A|=a$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and \n$|B|=b$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, there is an edge between \n$A$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and \n$B$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. McDiarmid and Yolov showed that if \n$\\delta (G)\\geq \\tilde \\alpha (G)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> then \n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is Hamiltonian, extending the famous theorem of Dirac which states that if \n$\\delta (G)\\geq |G|\/2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> then \n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is Hamiltonian. In 1973, Bondy showed that, unless \n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is a complete bipartite graph, Dirac\u2019s Hamiltonicity condition also implies pancyclicity, i.e., existence of cycles of all the lengths from \n$3$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> up to \n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. In this paper, we show that \n$\\delta (G)\\geq \\tilde \\alpha (G)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> implies that \n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is pancyclic or that \n$G=K_{\\frac{n}{2},\\frac{n}{2}}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, thus extending the result of McDiarmid and Yolov, and generalizing the classic theorem of Bondy.<\/jats:p>","DOI":"10.1017\/s0963548324000075","type":"journal-article","created":{"date-parts":[[2024,4,17]],"date-time":"2024-04-17T08:54:47Z","timestamp":1713344087000},"page":"554-563","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":3,"title":["A generalization of Bondy\u2019s pancyclicity theorem"],"prefix":"10.1017","volume":"33","author":[{"given":"Nemanja","family":"Dragani\u0107","sequence":"first","affiliation":[]},{"given":"David","family":"Munh\u00e1 Correia","sequence":"additional","affiliation":[]},{"given":"Benny","family":"Sudakov","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2024,4,17]]},"reference":[{"key":"S0963548324000075_ref19","doi-asserted-by":"crossref","first-page":"6908","DOI":"10.1093\/imrn\/rnx085","article-title":"Counting Hamilton decompositions of oriented graphs","volume":"2018","author":"Ferber","year":"2018","journal-title":"Int. Math. Res. Notices"},{"key":"S0963548324000075_ref21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00373-013-1377-x","article-title":"Recent advances on the Hamiltonian problem: Survey III","volume":"30","author":"Gould","year":"2014","journal-title":"Graph Comb."},{"key":"S0963548324000075_ref31","unstructured":"[31] K\u00fchn, D. and Osthus, D. (2014) Hamilton cycles in graphs and hypergraphs: an extremal perspective. In Proceedings of the International Congress of Mathematicians\u2014Seoul 2014. Vol. IV, pp. 381\u2013406. Kyung Moon Sa, Seoul."},{"key":"S0963548324000075_ref16","article-title":"Pancyclicity of Hamiltonian graphs","author":"Dragani\u0107","journal-title":"J. Eur. Math. Soc."},{"key":"S0963548324000075_ref6","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0095-8956(71)90016-5","article-title":"Pancyclic graphs I","volume":"11","author":"Bondy","year":"1971","journal-title":"J. Comb. Theory Ser. B"},{"key":"S0963548324000075_ref28","unstructured":"[28] Letzter, S. (2023) Pancyclicity of highly connected graphs, arXiv preprint arXiv: 2306.12579."},{"key":"S0963548324000075_ref33","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1016\/j.jctb.2012.04.002","article-title":"Cycle spectra of Hamiltonian graphs","volume":"102","author":"Milans","year":"2012","journal-title":"J. Comb. Theory Ser. B"},{"key":"S0963548324000075_ref13","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/s00493-009-2360-2","article-title":"Hamiltonian cycles in Dirac graphs","volume":"29","author":"Cuckler","year":"2009","journal-title":"Combinatorica"},{"key":"S0963548324000075_ref14","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1112\/plms\/s3-2.1.69","article-title":"Some theorems on abstract graphs","volume":"3","author":"Dirac","year":"1952","journal-title":"Proc. Lond. Math. Soc."},{"key":"S0963548324000075_ref36","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/978-3-319-24298-9_4","volume-title":"Recent trends in combinatorics","author":"Verstra\u00ebte","year":"2016"},{"key":"S0963548324000075_ref35","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0095-8956(88)90058-5","article-title":"A cycle structure theorem for Hamiltonian graphs","volume":"45","author":"Schmeichel","year":"1988","journal-title":"J. Comb. Theory Ser. B"},{"key":"S0963548324000075_ref34","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0012-365X(76)90068-6","article-title":"Hamiltonian circuits in random graphs","volume":"14","author":"P\u00f3sa","year":"1976","journal-title":"Discrete Math."},{"key":"S0963548324000075_ref5","first-page":"181","volume-title":"Pancyclic Graphs: Recent Results, Infinite and Finite Sets","author":"Bondy","year":"1973"},{"key":"S0963548324000075_ref2","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1002\/jgt.22716","article-title":"Divisible subdivisions","volume":"98","author":"Alon","year":"2021","journal-title":"J. Graph Theor."},{"key":"S0963548324000075_ref18","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0095-8956(84)90054-6","article-title":"New sufficient conditions for cycles in graphs","volume":"37","author":"Fan","year":"1984","journal-title":"J. Comb. Theory Ser. B"},{"key":"S0963548324000075_ref9","doi-asserted-by":"crossref","first-page":"113158","DOI":"10.1016\/j.disc.2022.113158","article-title":"Chen Hamilton-connected, vertex-pancyclic and bipartite holes","volume":"345","year":"2022","journal-title":"Discrete Math."},{"key":"S0963548324000075_ref23","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1016\/j.jctb.2010.02.001","article-title":"Pancyclicity of Hamiltonian and highly connected graphs","volume":"100","author":"Keevash","year":"2010","journal-title":"J. Comb. Theory Ser. B"},{"key":"S0963548324000075_ref8","doi-asserted-by":"crossref","first-page":"E70","DOI":"10.1017\/fms.2022.42","article-title":"Cycles of many lengths in Hamiltonian graphs","volume":"10","author":"Buci\u0107","year":"2022","journal-title":"Forum Math. Sigma"},{"key":"S0963548324000075_ref20","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/s00493-020-4434-0","article-title":"Cycle lengths in expanding graphs","volume":"41","author":"Friedman","year":"2021","journal-title":"Combinatorica"},{"key":"S0963548324000075_ref27","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.aim.2013.01.005","article-title":"Hamilton decompositions of regular expanders: a proof of Kelly\u2019s conjecture for large tournaments","volume":"237","author":"K\u00fchn","year":"2013","journal-title":"Adv. Math."},{"key":"S0963548324000075_ref4","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0095-8956(90)90133-K","article-title":"Hamiltonian degree conditions which imply a graph is pancyclic","volume":"48","author":"Bauer","year":"1990","journal-title":"J. Comb. Theory Ser. B"},{"key":"S0963548324000075_ref3","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1002\/rsa.21067","article-title":"Cycle lengths in sparse random graphs","volume":"61","author":"Alon","year":"2022","journal-title":"Random Struct. Algor."},{"key":"S0963548324000075_ref26","doi-asserted-by":"crossref","first-page":"3095","DOI":"10.1090\/S0002-9947-2014-05963-1","article-title":"Robust Hamiltonicity of Dirac graphs","volume":"366","author":"Krivelevich","year":"2014","journal-title":"Trans. Am. Math. Soc."},{"key":"S0963548324000075_ref22","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0012-365X(90)90130-A","article-title":"Chv\u00e1tal-Erd\u0151s conditions for paths and cycles in graphs and digraphs. A survey","volume":"84","author":"Jackson","year":"1990","journal-title":"Discrete Math."},{"key":"S0963548324000075_ref15","doi-asserted-by":"crossref","unstructured":"[15] Dragani\u0107, N. , Munh\u00e1 Correia, D. and Sudakov, B. (2023) Chv\u00e1tal-Erd\u0151s condition for pancyclicity. J. Assoc. Math. Res. (in press).","DOI":"10.5817\/CZ.MUNI.EUROCOMB23-052"},{"key":"S0963548324000075_ref32","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1002\/jgt.22114","article-title":"Hamilton cycles, minimum degree, and bipartite holes","volume":"86","author":"McDiarmid","year":"2017","journal-title":"J. Graph Theory"},{"key":"S0963548324000075_ref25","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1002\/jgt.10065","article-title":"Sparse pseudo-random graphs are Hamiltonian","volume":"42","author":"Krivelevich","year":"2003","journal-title":"J. Graph Theory"},{"key":"S0963548324000075_ref1","first-page":"173","volume-title":"Cycles in Graphs (Burnaby, B.C 1982)","volume":"115","author":"Ajtai","year":"1985"},{"key":"S0963548324000075_ref24","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1090\/S0894-0347-2010-00678-9","article-title":"The critical bias for the Hamiltonicity game is \n\n\n\n$(1+ o(1))n\/\\ln n$","volume":"24","author":"Krivelevich","year":"2011","journal-title":"J. Am. Math. Soc."},{"key":"S0963548324000075_ref11","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0012-365X(72)90079-9","article-title":"A note on Hamiltonian circuits","volume":"2","author":"Chv\u00e1tal","year":"1972","journal-title":"Discrete Math."},{"key":"S0963548324000075_ref12","first-page":"170","volume-title":"Proof of the 1-factorization and Hamilton decomposition conjectures","author":"Csaba","year":"2016"},{"key":"S0963548324000075_ref29","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/j.jctb.2017.08.002","article-title":"Cycle lengths and minimum degree of graphs","volume":"128","author":"Liu","year":"2018","journal-title":"J. Comb. Theory Ser. B"},{"key":"S0963548324000075_ref7","volume-title":"Longest Paths and Cycles in Graphs of High Degree","author":"Bondy","year":"1980"},{"key":"S0963548324000075_ref17","first-page":"187","volume-title":"Hypergraph Seminar","author":"Erd\u0151s","year":"1972"},{"key":"S0963548324000075_ref30","first-page":"1191","article-title":"A solution to Erd\u0151s and Hajnal\u2019s odd cycle problem","volume":"36","author":"Liu","year":"2023","journal-title":"J. Am. Math. Soc."},{"key":"S0963548324000075_ref10","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0095-8956(72)90020-2","article-title":"On Hamilton\u2019s ideals","volume":"12","author":"Chv\u00e1tal","year":"1972","journal-title":"J. Comb. Theory Ser. B"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000075","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T22:46:09Z","timestamp":1728427569000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000075\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,17]]},"references-count":36,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["S0963548324000075"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000075","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,17]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}