Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 134.43403
Autor: Erdös, Pál
Title: On some extremal problems in graph theory (In English)
Source: Isr. J. Math. 3, 113-116 (1965).
Review: Der Verf. beweist, daß für eine genügend große Konstante c jeder Graph G mit n Punkten und cn3/2 Kanten ein Sechseck x1,x2,x3,x4,x5,x6 enthält und dazu noch einen siebenten Punkt y, der mit x1,x3 und x5 verbunden ist. Würde G auch einen mit x2,x4 und x6 verbundenen Punkt z enthalten, so wäre in G auch das Kantennetz eines Würfels enthalten – doch dieses Problem bleibt auch weiterhin offen. Verf. beweist in vorliegender Arbeit eigentlich den folgenden allgemeineren Satz: Sei n > n0(k) und G ein Graph mit n Punkten und 10 · [k ½n3/2] Kanten dann enthält G einen Weg {x1,y1,x2,y2,...,xk,yk,xk+1} sowie die Kanten (x1,yi) und (y1,xj) für 2 \leq i \leq k und 3 \leq j \leq k+1. Der Fall k = 3 enthält den oben genannten Satz.
Reviewer: B.Andrásfai
Classif.: * 05C35 Extremal problems (graph theory)
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag