论文标题
增强Erdős-Gallai定理和伍德尔猜想的证明
A Strengthening of Erdős-Gallai Theorem and Proof of Woodall's Conjecture
论文作者
论文摘要
对于$ n $顶点上的2个连接的图$ g $和两个顶点$ x，y \ in v（g）$，我们证明，如果至少有$ \ frac {n-1} {n-1} {2} $ vertices in $ v（g）$ v）$ v n y y y y y y y y y y y y y y y y y $ \ y \ y \ y \ y \ y \ y \ y $这加强了1959年由于Erdős和Gallai引起的众所周知的定理。作为此结果的第一个应用，我们表明，具有$ N $ Vertices的2个连接图包含一个长度至少$ 2K $的周期，如果至少具有$ \ frac {n} {2} {2}+k $ k $ k $ k $ k $。这证实了伍德尔（Woodall）做出的1975年猜想。作为另一种应用，我们获得了一些结果，这些结果概括了Dirac，Erdős-Gallai，Bondy和Fujisawa等人的先前定理，这是Bazgan等人验证的Loebl-Komlós-SósSusenture的路径案例的简短证明。以及最长周期（用于大图）上的邦迪的猜想，这是由弗雷斯（Fraisse）和fournier确认的，并在bermond的猜想上取得了进展。
For a 2-connected graph $G$ on $n$ vertices and two vertices $x,y\in V(G)$, we prove that there is an $(x,y)$-path of length at least $k$ if there are at least $\frac{n-1}{2}$ vertices in $V(G)\backslash \{x,y\}$ of degree at least $k$. This strengthens a well-known theorem due to Erdős and Gallai in 1959. As the first application of this result, we show that a 2-connected graph with $n$ vertices contains a cycle of length at least $2k$ if it has at least $\frac{n}{2}+k$ vertices of degree at least $k$. This confirms a 1975 conjecture made by Woodall. As another applications, we obtain some results which generalize previous theorems of Dirac, Erdős-Gallai, Bondy, and Fujisawa et al., present short proofs of the path case of Loebl-Komlós-Sós Conjecture which was verified by Bazgan et al. and of a conjecture of Bondy on longest cycles (for large graphs) which was confirmed by Fraisse and Fournier, and make progress on a conjecture of Bermond.
