Cycle lengths in graphs of given minimum degree
Journal of Combinatorial Theory, Series B · 2026-09 · 180 · 111-150
DOI: 10.1016/j.jctb.2026.06.003 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Combinatorial Theory, Series B, 2026-09. Verfasst von Yandong Bai und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 21 Literaturangaben. Gefördert von: National Science Centre Poland, National Natural Science Foundation of China.
Abstract (Originalsprache)
We prove that if $G$ is a 2-connected graph with minimum degree at least $k\geqslant 4$, then (1) $G$ contains $k$ cycles whose lengths form an arithmetic progression with common difference one or two, unless $G\cong K_{k+1}$ or $K_{k,n-k}$; (2) $G$ contains cycles of lengths $\ell$ modulo $k$ for all even $\ell$, unless $G\cong K_{k+1}$ or $K_{k,n-k}$; (3) $G$ contains cycles of lengths $\ell$ modulo $k$ for all $\ell$, unless $G\cong K_{k+1}$ or $G$ is bipartite. In addition, we show that if $k$ is even and $G$ is 2-connected with minimum degree at least $k-1$ and order at least $k+2$, then $G$ contains cycles of lengths $\ell$ modulo $k$ for all even $\ell$. As a corollary, we determine the maximum number of edges in a graph that does not contain a cycle of length divisible by $k$ for all odd $k$.
Förderung
- National Science Centre Poland
- National Natural Science Foundation of China
Zitieren
APA
Bai, Y., Grzesik, A., Li, B., & Prorok, M. (2026). Cycle lengths in graphs of given minimum degree. Journal of Combinatorial Theory, Series B, 180, 111-150. https://doi.org/10.1016/j.jctb.2026.06.003
Vancouver
Bai Y, Grzesik A, Li B, Prorok M. Cycle lengths in graphs of given minimum degree. Journal of Combinatorial Theory, Series B. 2026;180:111-150. doi:10.1016/j.jctb.2026.06.003
BibTeX
@article{Bai2026,
author = {Bai, Yandong and Grzesik, Andrzej and Li, Binlong and Prorok, Magdalena},
title = {Cycle lengths in graphs of given minimum degree},
journal = {Journal of Combinatorial Theory, Series B},
year = {2026},
volume = {180},
pages = {111--150},
doi = {10.1016/j.jctb.2026.06.003}
}
EUVIMED