Stability in the Erdős-Gallai Theorems on cycles and paths

详细信息    查看全文

• 作者：Zoltá ; n Fü ; redi^a ; ¹ ; ^{zfuredi@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Alexandr Kostochka^b ; ^c ; ² ; ^{kostochk@math.uiuc.edu" class="auth_mail" title="E-mail the corresponding author} ; Jacques Verstraë ; te^d ; ³ ; ^{jverstra@math.ucsd.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Turá ; n problem ; Cycles ; Paths
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：121
• 期：Complete
• 页码：197-228
• 全文大小：678 K

文摘

The Erdős–Gallai Theorem states that for k≥2$k\ge 2$, every graph of average degree more than k−2$k-2$ contains a k-vertex path. This result is a consequence of a stronger result of Kopylov: if k   is odd, k=2t+1≥5$k=2t+1\ge 5$, n≥(5t−3)/2$n\ge (5t-3)/2$, and G is an n  -vertex 2-connected graph with at least $h(n,k,t):=\left(\begin{array}{c}k-t\\ 2\end{array}\right)+t(n-k+t)$ edges, then G contains a cycle of length at least k   unless G=H_n,k,t:=K_n−E(K_n−t)$G=H_{n,k,t}:=K_n-E(K_{n-t})$.

In this paper we prove a stability version of the Erdős–Gallai Theorem: we show that for all n≥3t>3$n\ge 3t>3$, and k∈{2t+1,2t+2}$k\in \{2t+1,2t+2\}$, every n-vertex 2-connected graph G   with e(G)>h(n,k,t−1)$e(G)>h(n,k,t-1)$ either contains a cycle of length at least k or contains a set of t   vertices whose removal gives a star forest. In particular, if k=2t+1≠7$k=2t+1\ne 7$, we show G⊆H_n,k,t$G\subseteq H_{n,k,t}$. The lower bound e(G)>h(n,k,t−1)$e(G)>h(n,k,t-1)$ in these results is tight and is smaller than Kopylov's bound h(n,k,t)$h(n,k,t)$ by a term of n−t−O(1)$n-t-O(1)$.