***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Date: Thursday 21st September, 3:00 in Fine Hall 224.
 
Speaker: Jie Ma (University of Science and Technology of China)

Title: Stability results in graphs of given circumference

In this talk we will discuss some Turan-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 the Erdos-Gallai theorem, 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,[c/2],c)) edges, with equality if and only 
if G equals W_{n,2,c} or W_{n,[c/2],c}. Recently, Furedi et al.  
obtained a stability version of Kopylov's theorem. They proved that 
if G is a 2-connected graph on n vertices with circumference c such  
that 9 < c < n and e(G) > max (f(n,3,c),f(n,[c/2]-1,c) ), then  
either G is a subgraph of W_{n,2,c} or W_{n,[c/2],c}, or c is odd 
and G is a subgraph of a member of two well-characterized families 
which we define as X_{n,c} and Y_{n,c}. We extend and refine their 
result by showing that if G is a 2-connected graph on n vertices with 
minimum degree at least k and circumference c such that 9 < c < n and  
e(G) > max (f(n,k+1,c),f(n,[c/2]-1,c)), then one of the following holds:

(i) G is a subgraph of W_{n,k,c} or W_{n,[c/2],c}, 

(ii) k=2, c is odd, and G is a subgraph of a member of  
X_{n,c} cup Y_{n,c}, or 

(iii) k > 2 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  
Furedi et al. as well as a recent result of Li et al. and independently, 
of Furedi 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.


Next week: Ron Aharoni

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)