{
  "id": "2408.15487",
  "version": "v1",
  "published": "2024-08-28T02:21:37.000Z",
  "updated": "2024-08-28T02:21:37.000Z",
  "title": "A strong structural stability of $C_{2k+1}$-free graphs",
  "authors": [
    "Zilong Yan",
    "Yuejian Peng"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "F\\\"uredi 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^*(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)^2k$, if $G$ is a $C_{2k+1}$-free $n$-vertex graph with $e(G)\\ge e(T^*(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\\limits_{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\\limits_{i=1}^{j-1} G_i$ for $2\\le j\\le p$ and $\\sum\\limits_{i=1}^p \\vert V(G_i)-V(G_i)\\cap V(B\\bigcup\\limits_{i=1}^{j-1} G_i) \\vert\\le r-1$. Furthermore, $\\sum\\limits_{i=1}^p \\vert V(G_i)-V(G_i)\\cap V(B\\bigcup\\limits_{i=1}^{j-1} G_i) \\vert= r-1$ if and only if $G=T^*(r, n)$. Let $d_2(G)=\\min\\{|T|: T\\subseteq V(G), G-T \\ \\text{is bipartite}\\}$ and $\\gamma_2(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 $\\gamma_2(G)\\le {\\lceil\\frac{r}{2}\\rceil \\choose 2}+{\\lfloor\\frac{r}{2}\\rfloor \\choose 2}$ 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 $\\gamma_2(G)\\le {\\lceil\\frac{r}{2}\\rceil \\choose 2}+{\\lfloor\\frac{r}{2}\\rfloor \\choose 2}$ 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-08-28T02:21:37.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "strong structural stability",
      "free graph",
      "structural stability result implies",
      "suspensions minus intersection points",
      "bipartite graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}