Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 126.39401
Autor: Erdös, Pál; Hajnal, András; Moon, J.W.
Title: A problem in graph theory (In English)
Source: Am. Math. Mon. 71, 1107-1110 (1964).
Review: Ein endlicher ungerichteter schlingenloser Graph ohne mehrfache Kanten wird (n,k)-Graph genannt, wenn er n Knotenpunkte besitzt und die Zahl seiner vollständigen Teilgraphen mit k Knotenpunkten (2 \leq k \leq n) bei Hinzufügen einer beliebigen weiteren Kante wächst. Die Verff. erkennen den Graphen, der genau alle die Kanten enthält, die mit einem oder zwei von k-2 festen Knotenpunkten inzidieren, als den einzigen minimalen, d. h. die Minimalzahl an Kanten besitzenden (n,k)-Graphen.
Sie benutzen dieses schöne Ergebnis zum Beweis einer Vermutung von P. Erdös und T. Gallai (Zbl 101.41001) bezüglich der Maximalzahl der Kanten eines kanten-p-kritischen (edge p-critical) Graphen (zur Definition vgl. die Arbeit) und weisen darauf hin, daß es – nur für (n,k)-Graphen formuliert, die ursprünglich keinen vollständigen Teilgraphen mit k Knotenpunkten besitzen – das duale Problem zu dem von {\it P. Turán (Zbl 055.17004); vgl. auch B. Andrásfai, Zbl 114.40001) behandelten beantwortet.
Schließlich formulieren sie als Vermutung einen entsprechenden Satz für paare (bipartite) Graphen, den der Ref. bewiesen hat [Wiss. Z. Tech. Hochsch. Ilmenau 12, 253-256 (1966; Zbl 148.18004)].
Reviewer: W.H.L.Wessel
Classif.: * 05C35 Extremal problems (graph theory)
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag