Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 194.25402
Autor: Erdös, Pál
Title: Über die in Graphen enthaltenen saturierten planaren Graphen. (On the saturated planar graphs contained in graphs.) (In German)
Source: Math. Nachr. 40, 13-17 (1969).
Review: G(n,m) bezeichne einen endlichen ungerichteten Graphen (ohne Schlingen und Mehrfachkanten) mit n Ecken und m Kanten. Die Frage wird untersucht, wie groß m, bei gegebenen n und s, mindestens sein muß, damit jedes G(n,m) einen ebenen Dreiecksgraphen mit \geq s Ecken enthält. (Ein ebener Dreiecksgraph ist ein Graph, der eine Einbettung in die Ebene besitzt derart, daß jedes der entstehenden Gebiete durch ein Dreieck des Graphen berandet wird.) Es gilt: Ist f(n) > 0 eine beliebige Funktion, so enthält jedes G(n,[n2/4]+f(n)) einen ebenen Dreiecksgraphen mit mehr als c1f(n)/n Ecken, wobei c1 > 0 eine absolute Konstante ist. Dieses Resultat ist abgesehen von dem Werte von c1 scharf.
Weitere Sätze beschäftigen sich mit dem Enthaltensein von Graphen, die aus einem m-Kreis C sowie k weiteren Ecken bestehen, die mit jeder Ecke von C durch eine Kante verbunden sind.
Reviewer: R.Halin
Classif.: * 05C10 Topological graph theory
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag