Size conditions for admissible or consecutive even cycles in graphs
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910096155475968 |
|---|---|
| author | Lin, Jifu |
| author_facet | Lin, Jifu |
| contents | In 2022, Gao, Huo, Liu, and Ma proved that every graph with minimum degree at least $k+1$ contains $k$ admissible cycles, where a set of $k$ cycles is said to be admissible if their lengths form an arithmetic progression with common difference one or two. In this paper, we provide a sharp size analogue of their result and characterize the extremal graphs attaining the lower bound. In 2016, Verstraëte conjectured that every $n$-vertex graph $G$ containing no $k$ cycles of consecutive even lengths has at most $(2k+1)(n-1)/2$ edges, with equality only if every block of $G$ is a clique of order $2k+1$. We prove this conjecture for $2k+2\leq n\leq 4k+1$, and in fact obtain a stronger result in this range. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_27975 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Size conditions for admissible or consecutive even cycles in graphs Lin, Jifu Combinatorics 05C38, 05C35 In 2022, Gao, Huo, Liu, and Ma proved that every graph with minimum degree at least $k+1$ contains $k$ admissible cycles, where a set of $k$ cycles is said to be admissible if their lengths form an arithmetic progression with common difference one or two. In this paper, we provide a sharp size analogue of their result and characterize the extremal graphs attaining the lower bound. In 2016, Verstraëte conjectured that every $n$-vertex graph $G$ containing no $k$ cycles of consecutive even lengths has at most $(2k+1)(n-1)/2$ edges, with equality only if every block of $G$ is a clique of order $2k+1$. We prove this conjecture for $2k+2\leq n\leq 4k+1$, and in fact obtain a stronger result in this range. |
| title | Size conditions for admissible or consecutive even cycles in graphs |
| topic | Combinatorics 05C38, 05C35 |
| url | https://arxiv.org/abs/2603.27975 |