Stability results in graphs of given circumference

Graph Theory Seminar
Thursday, September 28, 2017 - 13:30
1 hour (actually 50 minutes)
Skiles 005
University of Science and Technology of China
In this talk we will discuss some Tur\'an-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})$. Kopylov proved in 1977 that for $c\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 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 $10\leq c\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\geq 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\"{u}redi et al. as well as a recent result of Li et al. and independently, of F\"{u}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.