Cycle lengths in graphs of given minimum degree
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915598786625536 |
|---|---|
| author | Bai, Yandong Grzesik, Andrzej Li, Binlong Prorok, Magdalena |
| author_facet | Bai, Yandong Grzesik, Andrzej Li, Binlong Prorok, Magdalena |
| contents | In a graph, $k$ cycles are {\em admissible} if their lengths form an arithmetic progression with common difference one or two. Let $G$ be a 2-connected graph with minimum degree at least $k\geqslant 4$. We prove that
\begin{itemize}
\item [(1)] $G$ contains $k$ admissible cycles, unless $G\cong K_{k+1}$ or $K_{k,n-k}$;
\item [(2)] $G$ contains cycles of lengths $\ell$ modulo $k$ for all even $\ell$, unless $G\cong K_{k+1}$ or $K_{k,n-k}$;
\item [(3)] $G$ contains cycles of lengths $\ell$ modulo $k$ for all $\ell$, unless $G\cong K_{k+1}$ or $G$ is bipartite.
\end{itemize} 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$. These findings provide a stability analysis of the main results on cycle lengths in graphs of given minimum degree in [J. Gao, Q. Huo, C. Liu, J. Ma, A unified proof of conjectures on cycle lengths in graphs, International Mathematics Research Notices 2022 (10) (2022) 7615--7653]. As a corollary, we determine the maximum number of edges in a graph that does not contain a cycle of length 0 modulo $k$ for all odd $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_03085 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cycle lengths in graphs of given minimum degree Bai, Yandong Grzesik, Andrzej Li, Binlong Prorok, Magdalena Combinatorics In a graph, $k$ cycles are {\em admissible} if their lengths form an arithmetic progression with common difference one or two. Let $G$ be a 2-connected graph with minimum degree at least $k\geqslant 4$. We prove that \begin{itemize} \item [(1)] $G$ contains $k$ admissible cycles, unless $G\cong K_{k+1}$ or $K_{k,n-k}$; \item [(2)] $G$ contains cycles of lengths $\ell$ modulo $k$ for all even $\ell$, unless $G\cong K_{k+1}$ or $K_{k,n-k}$; \item [(3)] $G$ contains cycles of lengths $\ell$ modulo $k$ for all $\ell$, unless $G\cong K_{k+1}$ or $G$ is bipartite. \end{itemize} 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$. These findings provide a stability analysis of the main results on cycle lengths in graphs of given minimum degree in [J. Gao, Q. Huo, C. Liu, J. Ma, A unified proof of conjectures on cycle lengths in graphs, International Mathematics Research Notices 2022 (10) (2022) 7615--7653]. As a corollary, we determine the maximum number of edges in a graph that does not contain a cycle of length 0 modulo $k$ for all odd $k$. |
| title | Cycle lengths in graphs of given minimum degree |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2511.03085 |