Every 2-connected n-vertex graph with more than floor((3n-1)/2) edges contains a cycle whose length is a multiple of 4, and this bound is sharp for all n at least 12.
A note on two cycles of consecutive even lengths in graphs
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
Bondy and Vince proved that a graph of minimum degree at least three contains two cycles whose lengths differ by one or two, which was conjectured by Erd\H{o}s. Gao, Li, Ma and Xie gave an average degree counterpart of Bondy-Vince's result, stating that every $n$-vertex graph with at least $\frac{5}{2}(n-1)$ edges contains two cycles of consecutive even lengths, unless $4|(n-1)$ and every block of $G$ is a clique $K_5$. This confirms the case $k=2$ of Verstra\"ete's conjecture, which states that every $n$-vertex graph without $k$ cycles of consecutive even lengths has edge number $e(G)\leq\frac{1}{2}(2k+1)(n-1)$, with equality if and only if every block of $G$ is a clique of order $2k+1$. Sudakov and Verstra\"{e}te further conjectured that if $G$ is a graph with maximum number of edges that does not contain $k$ cycles of consecutive even lengths, then every block of $G$ is a clique of order at most $2k+1$. In this paper, we prove the case $k=2$ for Sudakov-Verstra\"{e}te's conjecture, by extending the results of Gao, Li, Ma and Xie.
citation-role summary
citation-polarity summary
fields
math.CO 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
On $2$-connected graphs avoiding cycles of length $0$ modulo $4$
Every 2-connected n-vertex graph with more than floor((3n-1)/2) edges contains a cycle whose length is a multiple of 4, and this bound is sharp for all n at least 12.