论文标题
Dirac定理的稳定版本及其用于广义Turán问题的应用
Stability version of Dirac's theorem and its applications for generalized Turán problems
论文作者
论文摘要
1952年，狄拉克（Dirac）证明，最低度$ k+1 $的每$ 2 $连接的$ n $ vertex图包含一个长度的周期，至少$ \ min \ {n，2（k+1）\} $。在这里，我们通过表征最低度$ k $的这些图表，最多$ 2K+1 $来获得此结果的稳定版本。 我们通过获得广义的Turán数字来介绍上述结果的应用。特别是，对于所有$ \ ell \ geq 5 $，我们确定有必要的五循环和四个周期的副本，以确保图形的圆周大于$ \ ell $。此外，我们使用稳定性结果给出了Luo定理的新证明。
In 1952, Dirac proved that every $2$-connected $n$-vertex graph with the minimum degree $k+1$ contains a cycle of length at least $\min\{n, 2(k+1)\}$. Here we obtain a stability version of this result by characterizing those graphs with minimum degree $k$ and circumference at most $2k+1$. We present applications of the above-stated result by obtaining generalized Turán numbers. In particular, for all $\ell \geq 5$ we determine how many copies of a five-cycle as well as four-cycle are necessary to guarantee that the graph has circumference larger than $\ell$. In addition, we give a new proof of Luo's Theorem for cliques using our stability result.
