Stability Results on the Circumference of a Graph

In this paper, we extend and refine previous Turan-type results on graphs with a given circumference. Let W-n,W- k,W- c be the graph obtained from a clique Kc - 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,W- k,W- c). Improving a celebrated theorem of Erdos and Gallai [8], Kopylov [18] 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,Lc2<SIC> RIGHT FLOOR,c)} edges, with equality if and only if G is isomorphic to W-n,W-2,W-c or Wn,Lc2<SIC> RIGHT FLOOR,c. Recently, Furedi et al. [15,14] 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 <= c < n and e(G)>max{f(n,3,c),f(n,Lc2<SIC> RIGHT FLOOR-1,c)}, or c is odd and G is a subgraph of a member of two well-characterized families which we define as chi(n,c) and gamma(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 <= c < n and Wn,Lc2<SIC> RIGHT FLOOR,c = 2, is odd, and is a subgraph of a member of ?gamma, or >= 3 and is a subgraph of the union of a clique +1 and some cliques +1's, where any two cliques share the same two vertices. This provides a unified generalization of the above result of Furedi et al. [15,14] as well as a recent result of Li et al. [20] and independently, of Furedi et al. [12] on non-Hamiltonian graphs. A refinement and some variants of this result are also obtained. Moreover, we prove a stability result on a classical theorem of Bondy [2] on the circumference. We use a novel approach, which combines several proof ideas including a closure operation and an edge-switching technique. We will also discuss some potential applications of this approach for future research.