New sufficient conditions for cycles in graphs (Q801082): Difference between revisions

Es wird ein Ergebnis über längste Kreise, insbesondere Hamiltonkreise, in Graphen vorgestellt. Dieses Resultat ist eine Verschärfung der Kriterien von Dirac, Ore, Posa, Bondy, Bermond und Linial. Für gegebenen Graph G bezeichne \(S_ j\) die Menge der Ecken v mit \(d(v)\leq j.\) Satz: Sei G 2-zusammenhängend und \(3\leq c\leq | G|;\) es gelte: \(j<k,\quad j+k<c+1,\quad | S_ j| \geq j\) und \(| S_{k-1}| \geq k\Rightarrow\) je zwei Ecken in \(S_ j\) haben einen Abstand ungleich zwei. Dann gibt es einen Kreis mit mindestens c Kanten. Im Beweis wird ein Ergebnis von \textit{J. A. Bondy} [Discrete Math. 1, 121-132 (1971; Zbl 0224.05120)] benutzt. Im Fall \(c=| G|\) ist der Beweis einfacher und wird ausgeführt für folgendes Korollar: Sei G 2-zusammenhängend mit \(n\geq 3\) Ecken. Gilt \(\max (d(u),d(v))\geq n/2\) für je zwei Ecken u,v vom Abstand 2, so besitzt G einen Hamiltonkreis.