Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 117.41201
Autor: Bollobás, Béla; Erdös, Pál
Title: Über graphentheoretische Extremalprobleme. (Extremal problems in graph theory.) (In Hungarian)
Source: Mat. Lapok 13, 143-152 (1962).
Review: Es bezeichne Gk(n) einen solchen Graphen, der aus n Knotenpunkten und k Kanten besteht und der keine Schlingen und mehrfache Kanten enthält. Die Arbeit beschäftigt sich mit der Bestimmung solcher minimalen g(n)-Werte, für die der Graph G(n)g(n) stets Teilgraphen mit gewissen vorgeschriebenen Eigenschaften enthält. Die Arbeit enthält zwei Beweise für den folgenden, von L. Pósa vermuteten Satz: Es sei f(2m) = 3m-1. f(2m+1) = 3m+1 (m = 1,2,...). Der Graph G(n)f(n) (n \geq 4) enthält stets einen solchen Teilgraphen, der aus einem Kreis K, aus einem nicht aus K liegenden Knotenpunkt x und aus zwei solchen Kanten besteht, die x mit zwei Knotenpunkten von K verbinden.
Classif.: * 05C35 Extremal problems (graph theory)
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag