×

zbMATH — the first resource for mathematics

Graphs with prescribed degrees of vertices. (Graphen mit Punkten vorgeschriebenen Grades.) (Hungarian) Zbl 0103.39701
Eine Folge \((a_1,...,a_n)\) nichtnegativer ganzer Zahlen heißt regulär, wenn \(a_1 \geq \cdots \geq a_n \geq 0\). Eine Folge (\(a_1,...,a_n\)) wird realisierbar genannt, wenn es einen Graphen (ohne Ein- und Zweiecke) mit \(n\) Punkten \(P_1,...,P_n\) gibt, so daß der Grad jedes \(P_i\) die Zahl \(a_i\) ist. Satz: Eine reguläre Folge ist genau dann realisierbar, wenn \(a_1 + \cdots + a_n\) gerade und \[ (a_1 + \cdots + a_j)-j(j-1) \leq (k-j)j + (a_{k+1} + \cdots + a_n) \] für jedes \(j\) und \(k\) (falls \(1 \leq j \leq n-1\), \(j\leq k \leq n)\) gilt. Dieser Satz wird sowohl unmittelbar bewiesen, als auch aus einem Satz von W.T.Tutte (dies. Zbl 0049.24202) abgeleitet.
[Bemerkungen des Ref.: S. 266, Zeile 6 lies \(\nu_j^* \geq \nu_j\) statt \(\nu_j^* = \nu_j\), S. 268, Zeile 5 lies \(S_k-S_j\) statt \(S_{k-j}\), S. 270, Zeile 10 lies \(a_n \geq 1\) statt \(a_n > 1\). Die erste dieser Verbesserungen macht einige (nicht wesentliche) Korrekturen in den letzten Überlegungen des Paragraphen 4 notwendig.]
Reviewer: A.Ádám

MSC:
05C99 Graph theory
Keywords:
topology
PDF BibTeX XML Cite