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.