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}
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}
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.
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.