Stability results on the circumference of a graph

Abstract

In this paper, we extend and refine previous Turán-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ő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üredi 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\le 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\le 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\ge 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üredi et al. as well as a recent result of Li et al. and independently, of Füredi et al. on non-Hamiltonian graphs. Moreover, we prove a stability result on a classical theorem of Bondy on the circumference.

31 pages, to appear in Combinatorica

References in corpus (1)

• Spectral analogues of Erdős' and Moon-Moser's theorems on Hamilton cycles

Cited by in corpus (3)

• Extremal graphs for the odd prism
• A Strengthening of Erdős-Gallai Theorem and Proof of Woodall's Conjecture
• Stability in Bondy's theorem on paths and cycles