Direkt zum Inhalt

Lexikon der Mathematik: Chvátal-Erdős, Satz von

Aussage innerhalb der Graphentheorie über Hamiltonsche Graphen.

Ein Graph G ist Hamiltonsch, falls κ(G) > α(G) gilt, wobei κ(G) die Zusammenhangszahl und α(G) die Unabhängigkeitszahl von G bedeuten. Darüber hinaus zeigten V. Chvátal und P. Erdős in ihrer 1972 publizierten Arbeit, daß G unter der Voraussetzung \begin{eqnarray}\kappa (G)\ge \alpha (G)-1\end{eqnarray} einen Hamiltonschen Weg besitzt, und G ein Hamilton-zusammenhängender Graph ist, falls \begin{eqnarray}\kappa (G)\ge \alpha (G)+1\end{eqnarray} gilt.

Lesermeinung

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

Partnervideos