{
  "id": "1708.00704",
  "version": "v1",
  "published": "2017-08-02T11:30:02.000Z",
  "updated": "2017-08-02T11:30:02.000Z",
  "title": "Stability results on the circumference of a graph",
  "authors": [
    "Jie Ma",
    "Bo Ning"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "In this paper, we extend and refine previous Tur\\'an-type results on graphs with a given circumference. Let $W_{n,k,c}$ be the graph obtained from a clique $K_{c-k+1}$ by adding $n-(c-k+1)$ isolated vertices each joined to the same $k$ vertices of the clique, and let $f(n,k,c)=e(W_{n,k,c})$. Improving a celebrated theorem of Erd\\H{o}s and Gallai, Kopylov proved that for $c<n$, any 2-connected graph $G$ on $n$ vertices with circumference $c$ has at most $\\max\\{f(n,2,c),f(n,\\lfloor\\frac{c}{2}\\rfloor,c)\\}$ edges. Recently, F\\\"uredi et al. proved a stability version of Kopylov's theorem. Their main result states that if $G$ is a 2-connected graph on $n$ vertices with circumference $c$ such that $10\\leq c<n$ and $e(G)>\\max\\{f(n,3,c),f(n,\\lfloor\\frac{c}{2}\\rfloor-1,c)\\}$, then either $G$ is a subgraph of $W_{n,2,c}$ or $W_{n,\\lfloor\\frac{c}{2}\\rfloor,c}$, or $c$ is odd and $G$ is a subgraph of a member of two well-characterized families which we define as $\\mathcal{X}_{n,c}$ and $\\mathcal{Y}_{n,c}$. We prove that if $G$ is a 2-connected graph on $n$ vertices with minimum degree at least $k$ and circumference $c$ such that $10\\leq c<n$ and $e(G)>\\max\\{f(n,k+1,c),f(n,\\lfloor\\frac{c}{2}\\rfloor-1,c)\\}$, then one of the following holds: (i) $G$ is a subgraph of $W_{n,k,c}$ or $W_{n,\\lfloor\\frac{c}{2}\\rfloor,c}$, (ii) $k=2$, $c$ is odd, and $G$ is a subgraph of a member of $\\mathcal{X}_{n,c}\\cup \\mathcal{Y}_{n,c}$, or (iii) $k\\geq 3$ and $G$ is a subgraph of the union of a clique $K_{c-k+1}$ and some cliques $K_{k+1}$'s, where any two cliques share the same two vertices. This provides a unified generalization of the above result of F\\\"uredi et al. as well as a recent result of Li et al. and independently, of F\\\"uredi et al. on non-Hamiltonian graphs. Moreover, we prove a stability result on a classical theorem of Bondy on the circumference.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-08-02T11:30:02.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "stability result",
      "circumference",
      "main result states",
      "non-hamiltonian graphs",
      "cliques share"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}