Combinatorics Seminar

When: Sunday, December 10, 10am
Where: Schreiber 309
Speaker: Jie Ma, University of Science and Technology of China
Title: Stability results in graphs of given circumference

Abstract:

In this talk we will discuss some Turan-type results on graphs with a given circumference. Let Wn,k,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(Wn,k,c).

Let t be the floor of c/2. Kopylov proved in 1977 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,t,c)} edges, with equality if and only if G equals Wn,2,c or Wn,t,c. Recently, Füredi et al. obtained a stability version of Kopylov's theorem. We extend and refine their result by imposing an extra parameter, namely, the minimum degree.

Our main result implies that if G is an n-vertex 2-connected graph with minimum degree at least k and circumference c such that 10≤c<n and e(G)>max{f(n,k+1,c),f(n,t-1,c)}, then one of the following holds:

(i) G is a subgraph of Wn,k,c or Wn,t,c,

(ii) if k=2 and c is odd, then G is a member in two well-defined families of graphs, or

(iii) if k≥2, then G is a subgraph of the union of a clique Kc-k+1 and some cliques Kk+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. We use a novel approach, which combines several proof ideas including a closure operation and an edge-switching technique.

This is a joint work with Bo Ning.