Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 103.39701
Autor: Erdös, Pál; Gallai, Tibor
Title: Graphen mit Punkten vorgeschriebenen Grades. (Graphs with points of prescribed degree) (In Hungarian)
Source: Mat. Lapok 11, 264-274 (1961).
Review: Eine Folge (a1,...,an) nichtnegativer ganzer Zahlen heißt regulär, wenn a1 \geq ··· \geq an \geq 0. Eine Folge (a1,...,an) wird realisierbar genannt, wenn es einen Graphen (ohne Ein- und Zweiecke) mit n Punkten P1,...,Pn gibt, so daß der Grad jedes Pi die Zahl ai ist. Satz: Eine reguläre Folge ist genau dann realisierbar, wenn a1+···+an gerade und (a1+···+aj)-j(j-1) \leq (k-j)j+(ak+1+···+an) 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 049.24202) abgeleitet.
[Bemerkungen des Ref.: S. 266, Zeile 6 lies \nuj^* \geq \nuj statt \nuj^* = \nuj, S. 268, Zeile 5 lies Sk-Sj statt Sk-j, S. 270, Zeile 10 lies an \geq 1 statt an > 1. Die erste dieser Verbesserungen macht einige (nicht wesentliche) Korrekturen in den letzten Überlegungen des Paragraphen 4 notwendig.]
Reviewer: A.Ádám
Classif.: * 05C99 Graph theory
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag