A strong structural stability of $C_{2k+1}$-free graphs

Abstract

Füredi and Gunderson showed that $ex(n,C_{2k+1})$ is achieved only on $K_{\lfloor \frac{n}{2}\rfloor ,\lceil \frac{n}{2}\rceil }$ if $n\ge 4k-2$. It is natural to study how far a $C_{2k+1}$-free graph is from being bipartite.Let $T^{\ast }(r,n)$ be obtained by adding a suspension $K_r$ with $1$ suspension point to $K_{\lfloor \frac{n-r+1}{2}\rfloor ,\lceil \frac{n-r+1}{2}\rceil }$. We show that for integers $r,k$ with $3\le r\le 2k-4$ and $n\ge 20(r+2{)}^{2}k$, if $G$ is a $C_{2k+1}$-free $n$-vertex graph with $e(G)\ge e(T^{\ast }(r,n))$, then $G$ is obtained by adding suspensions to a bipartite graph one by one and the total number of vertices in all suspensions minus intersection points is no more than $r-1$. In other words, $G=B\bigcup _{i=1}^p{G}_i$, where $B$ is a bipartite graph, $G_1$ is a suspension to $B$, $G_j$ is a suspension to $B\bigcup _{i=1}^{j-1}{G}_i$ for $2\le j\le p$ and $\sum _{i=1}^p|V(G_i)-V(G_i)\cap V(B\bigcup _{i=1}^{j-1}{G}_i)|\le r-1$. Furthermore, $\sum _{i=1}^p|V(G_i)-V(G_i)\cap V(B\bigcup _{i=1}^{j-1}{G}_i)|=r-1$ if and only if $G=T^{\ast }(r,n)$. Let $d_2(G)=\min \{|T|:T\subseteq V(G),G-T\text{is bipartite}\}$ and ${\hat{I}}_2^3(G)=\min \{|E|:E\subseteq E(G),G-E\text{is bipartite}\}$. Our structural stability result implies that $d_2(G)\le r-1$ and ${\hat{I}}_2^3(G)\le \left(\genfrac{}{}{0ex}{}{\lceil \frac{r}{2}\rceil }{2}\right)+\left(\genfrac{}{}{0ex}{}{\lfloor \frac{r}{2}\rfloor }{2}\right)$ under the same condition, which is a recent result of Ren-Wang-Wang-Yang [SIAM J. Discrete Math. 38 (2024)]. They proved $d_2(G)\le r-1$ and ${\hat{I}}_2^3(G)\le \left(\genfrac{}{}{0ex}{}{\lceil \frac{r}{2}\rceil }{2}\right)+\left(\genfrac{}{}{0ex}{}{\lfloor \frac{r}{2}\rfloor }{2}\right)$ separately. We introduce a new concept strong-$2k$-core which is the key that we can give a stronger structural stability result but a simpler proof.