Direkt zum Inhalt

Lexikon der Mathematik: Gradfolge eines Graphen

zu einem Graphen G mit der Eckenmeng E(G) ={x1, x2,…,xn} die Folge \begin{eqnarray}{d}_{G}({x}_{1}),\,{d}_{G}({x}_{2}),\ldots,{d}_{G}({x}_{n})\,.\end{eqnarray}

Eine Folge nicht negativer ganzer Zahlen d1, d2,…,dn heißt graphisch, wenn ein Graph existiert, der diese Folge als Gradfolge besitzt. Es ergibt sich unmittelbar die interessante Frage, welche Folgen graphisch sind. Durch sukzessives Anwenden der folgenden notwendigen und hinreichenden Bedingung von V. Havel (1955) und S.L. Hakimi (1962) läßt sich leicht entscheiden, ob eine Folge graphisch ist.

Eine gegebene Folge nicht negativer ganzer Zahlen d1d2 ≥…≥ dn ist genau dann graphisch, wenn die Folge \begin{eqnarray}{d}_{1}\,-\,1,\ldots,{d}_{{d}_{n}}\,-\,1,\,{d}_{{d}_{n+1}},\ldots,{d}_{n-1}\end{eqnarray}graphisch ist.

Bei der praktischen Anwendung des Kriteriums von Havel und Hakimi sollte man allerdings zunächst testen, ob die gegebene Folge das Hand-schlaglemma erfüllt, also ob \(\displaystyle {\sum }_{i=1}^{n}{d}_{i}\) eine gerade Zahl ist.

Ein weitere wichtige Charakterisierung graphischer Folgen wurde 1960 von P. Erdős und T. Gallai präsentiert:

Eine gegebene Folge nicht negativer ganzer Zahlen d1d2 ≥…≥ dn ist genau dann graphisch, wenn \(\displaystyle {\sum }_{i=1}^{n}{d}_{i}\) gerade ist, und wenn \begin{eqnarray}\displaystyle \sum _{i=1}^{p}{d}_{i}\,\le \,p(p\,-\,1)\,+\,\displaystyle \sum _{i=p+1}^{n}\min \{p,{d}_{i}\}\end{eqnarray}für alle p mit 1 ≤ pn 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