Direkt zum Inhalt

Lexikon der Mathematik: panzyklischer Graph

ein Graph G der Ordnung n, der Kreise aller Längen p mit 3 ≤ pn besitzt.

Als Verallgemeinerung des klassischen Satzes von Ore bewies A. Bondy 1971 hierzu das folgende Resultat.

Ist G ein Graph der Ordnung n ≥ 3, und gilt für je zwei nicht adjazente Ecken x und y die Ungleichung \begin{eqnarray}{d}_{G}(x)+{d}_{G}(y)\ge n,\end{eqnarray}so ist G entweder panzyklisch, oder n ist gerade und G ist isomorph zum vollständigen bipartiten Graphen Kn/2,n/2.

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.