A generalization of Bondy’s pancyclicity theorem

EUROCOMB’23

Abstract
The bipartite independence number of a graph $G$, denoted as $\tilde\alpha(G)$, is the minimal number $k$ such that there exist positive integers $a$ and $b$ with $a+b=k+1$ with the property that for any two sets $A,B\subseteq V(G)$ with $|A|=a$ and $|B|=b$, there is an edge between $A$ and $B$. McDiarmid and Yolov showed that if $\delta(G)\geq\tilde \alpha(G)$ then $G$ is Hamiltonian, extending the famous theorem of Dirac which states that if $\delta(G)\geq |G|/2$ then $G$ is Hamiltonian. In 1973, Bondy showed that, unless $G$ is a complete bipartite graph, Dirac‘s Hamiltonicity condition also implies pancyclicity, i.e., existence of cycles of all the lengths from $3$ up to $n$. In this paper we show that $\delta(G)\geq\tilde \alpha(G)$ implies that $G$ is pancyclic or that $G=K_{\frac{n}{2},\frac{n}{2}}$, thus extending the result of McDiarmid and Yolov, and generalizing the classic theorem of Bondy.

Pages:
368–372
References

M. Ajtai, J. Komlós, and E. Szemerédi. First occurrence of Hamilton cycles in random graphs. In Cycles in graphs (Burnaby, B.C., 1982), Vol. 115, North-Holland Mathematical Studies, North-Holland, Amsterdam, 115:173-178, 1985.
https://doi.org/10.1016/S0304-0208(08)73007-X

N. Alon and M. Krivelevich. Divisible subdivisions. Journal of Graph Theory, 98(4):623-629, 2021.
https://doi.org/10.1002/jgt.22716

Y. Alon, M. Krivelevich, and E. Lubetzky. Cycle lengths in sparse random graphs. Random Structures & Algorithms, 61(3):444-461, 2022.
https://doi.org/10.1002/rsa.21067

D. Bauer and E. Schmeichel. Hamiltonian degree conditions which imply a graph is pancyclic. Journal of Combinatorial Theory, Series B, 48(1):111-116, 1990.
https://doi.org/10.1016/0095-8956(90)90133-K

J. A. Bondy. Pancyclic graphs: recent results, infinite and finite sets. In Colloq. Math. Soc. János Bolyai, Keszthely, pp. 181-187, 1973.

J. A. Bondy. Pancyclic graphs I. Journal of Combinatorial Theory, Series B, 11(1):80-84, 1971.
https://doi.org/10.1016/0095-8956(71)90016-5

J. A. Bondy. Longest paths and cycles in graphs of high degree. Department of Combinatorics and Optimization, University of Waterloo, 1980.

M. Bucić, L. Gishboliner, and B. Sudakov. Cycles of many lengths in Hamiltonian graphs. Forum of Mathematics, Sigma, 10, E70, 2022.
https://doi.org/10.1017/fms.2022.42

M. Chen Hamilton-connected, vertex-pancyclic and bipartite holes. Discrete Mathematics, 345(12):113158, 2022.
https://doi.org/10.1016/j.disc.2022.113158

V. Chvátal. On Hamilton's ideals. Journal of Combinatorial Theory, Series B, 12(2):163-168, 1972.
https://doi.org/10.1016/0095-8956(72)90020-2

V. Chvátal and P. Erdős. A note on Hamiltonian circuits. Discrete Mathematics, 2(2):111-113, 1972.
https://doi.org/10.1016/0012-365X(72)90079-9

B. Csaba, D. Kühn, A. Lo, D. Osthus, and A. Treglown. Proof of the 1-factorization and Hamilton decomposition conjectures. Memoirs of the American Mathematical Society, 244, monograph 1154, 170 pages, 2016.
https://doi.org/10.1090/memo/1154

B. Cuckler and J. Kahn. Hamiltonian cycles in Dirac graphs. Combinatorica, 29(3):299-326, 2009.
https://doi.org/10.1007/s00493-009-2360-2

G. A. Dirac. Some theorems on abstract graphs. Proceedings of the London Mathematical Society, 3(1):69-81, 1952.
https://doi.org/10.1112/plms/s3-2.1.69

N. Draganić, D. Munhá Correia and B. Sudakov. Chvátal-Erdős condition for pancyclicity. arXiv:2301.10190 2023.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-052

N. Draganić, D. Munhá Correia and B. Sudakov. Pancyclicity of Hamiltonian graphs. arXiv:2209.03325 2022.

G. H. Fan. New sufficient conditions for cycles in graphs. Journal of Combinatorial Theory, Series B, 37(3):221-227, 1984.
https://doi.org/10.1016/0095-8956(84)90054-6

A. Ferber, E. Long, and B. Sudakov. Counting Hamilton decompositions of oriented graphs. International Mathematics Research Notices, 2018(22):6908-6933, 2018.
https://doi.org/10.1093/imrn/rnx085

L. Friedman and M. Krivelevich. Cycle lengths in expanding graphs. Combinatorica, 41(1):53-74, 2021.
https://doi.org/10.1007/s00493-020-4434-0

R. J. Gould. Recent advances on the Hamiltonian problem: Survey III. Graphs and Combinatorics, 30(1):1-46, 2014.
https://doi.org/10.1007/s00373-013-1377-x

H. Liu and R. Montgomery. A solution to Erdős and Hajnal's odd cycle problem. arXiv preprint arXiv:2010.15802, 2020.

B. Jackson and O. Ordaz. Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey. Discrete mathematics, 84(3):241-254, 1990.
https://doi.org/10.1016/0012-365X(90)90130-A

P. Keevash and B. Sudakov. Pancyclicity of Hamiltonian and highly connected graphs. Journal of Combinatorial Theory, Series B, 100(5):456-467, 2010.
https://doi.org/10.1016/j.jctb.2010.02.001

M. Krivelevich. The critical bias for the Hamiltonicity game is (1 + o(1))n/ ln n. Journal of the American Mathematical Society, 24(1):125-131, 2011.
https://doi.org/10.1090/S0894-0347-2010-00678-9

M. Krivelevich and B. Sudakov. Sparse pseudo-random graphs are Hamiltonian. J. Graph Theory, 42(1):17-33, 2003.
https://doi.org/10.1002/jgt.10065

M. Krivelevich, C. Lee, and B. Sudakov. Robust Hamiltonicity of Dirac graphs. Transactions of the American Mathematical Society, 366(6):3095-3130, 2014.
https://doi.org/10.1090/S0002-9947-2014-05963-1

D. Kühn and D. Osthus. Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments. Advances in Mathematics, 237:62-146, 2013.
https://doi.org/10.1016/j.aim.2013.01.005

C.-H. Liu and J. Ma. Cycle lengths and minimum degree of graphs. Journal of Combinatorial A generalization of Bondy's pancyclicity theorem 5 Theory, Series B, 128:66-95, 2018.
https://doi.org/10.1016/j.jctb.2017.08.002

D. Kühn and D. Osthus. Hamilton cycles in graphs and hypergraphs: an extremal perspective. In Proceedings of the International Congress of Mathematicians-Seoul 2014. Vol. IV, pp. 381-406. Kyung Moon Sa, Seoul, 2014.

C. McDiarmid and N. Yolov. Hamilton cycles, minimum degree, and bipartite holes. Journal of Graph Theory, 86(3):277-285, 2017.
https://doi.org/10.1002/jgt.22114

K. G. Milans, F. Pfender, D. Rautenbach, F. Regen, and D. B. West. Cycle spectra of Hamiltonian graphs. Journal of Combinatorial Theory, Series B, 102(4):869-874, 2012.
https://doi.org/10.1016/j.jctb.2012.04.002

L. Pósa, Hamiltonian circuits in random graphs. Discrete Mathematics, 14(4):359-364, 1976.
https://doi.org/10.1016/0012-365X(76)90068-6

E. F. Schmeichel and S. L. Hakimi. A cycle structure theorem for Hamiltonian graphs. Journal of Combinatorial Theory, Series B, 45(1):99-107, 1988.
https://doi.org/10.1016/0095-8956(88)90058-5

J. Verstraëte. Extremal problems for cycles in graphs. In Recent trends in combinatorics, pp. 83-116. Springer, 2016.
https://doi.org/10.1007/978-3-319-24298-9_4

Metrics

0

Views

0

PDF views