Direkt zum Inhalt

Lexikon der Mathematik: Bondy-Chvátal, Satz von

hinreichendes Kriterium dafür, daß ein Graph einen Hamiltonschen Kreis besitzt.

Im Jahre 1960 hat O. Ore folgendes nützliche Lemma präsentiert. Sind u und v zwei nicht adjazente Ecken eines Graphen G der Ordnung n mit

\begin{eqnarray}{d}_{G}(u)+{d}_{G}(\upsilon )\ge n,\end{eqnarray}

so ist G genau dann Hamiltonsch, wenn G + uv Hamiltonsch ist.

J.A. Bondy und V. Chvatal benutzten 1976 dieses Lemma von Ore als Grundlage für ihre Definition der sogenannten Hamiltonschen Hülle.

Es sei G ein Graph der Ordnung n. Bildet man ausgehend von G = G1 eine längstmögliche Folge von Graphen (Gi)i=1,2,…,p, indem man beim Übergang von Gi zu Gi+1 jeweils eine Kante k = uv hinzufügt, die zwei in Gi nicht adjazente Ecken u und v mit \({d}_{{G}_{i}}(u)+{d}_{{G}_{i}}(\upsilon )\ge n\) verbindet, so zeigten Bondy und Chvatal, daß Gp unabhängig von der Reihenfolge der hinzugefügten Kanten ist. Daher ist Gp ein wohldefinierter Graph, der den Namen Hamiltonsche Hülle trägt, in Zeichen

\begin{eqnarray}{G}_{p}=C{l}_{n}(G).\end{eqnarray}

Aus dem Lemma von Ore folgt nun sofort, daß G genau dann Hamiltonsch ist, wenn Cln(G) Hamiltonsch ist. Insbesondere besitzt G einen Hamiltonschen Kreis, wenn Cln(G) der vollständige Graph Kn ist, falls n ≥ 3 gilt.

Darüber hinaus haben Bondy und Chvátal auch für andere Eigenschaften von Graphen, wie z. B. k-facher Zusammenhang oder die Existenz eines k-Faktors, sogenannte Hüllenkonzepte entwickelt.

  • Die Autoren
- Prof. Dr. Guido Walz

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.

Partnerinhalte

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