Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 144.23302
Autor: Erdös, Pál; Rényi, Alfréd; Sós, Vera T.
Title: On a problem of graph theory (In English)
Source: Stud. Sci. Math. Hungar. 1, 215-235 (1966).
Review: Die in vorliegender Arbeit behandelten Graphen sind ungerichtet und enthalten keine Schlingen. Betrachten wir jene n Punkte enthaltenden Graphen, in welchen die maximale Gradzahl k ist, und deren Durchmesser nicht größer als d ist. Die Kantenanzahl der Graphen minimaler Kantenanzahl unter diesen (der "extremen Graphen") soll mit Fd(n,k) bezeichnet werden. Die Verff. bestimmen im Fall 1/2 n \leq k \leq n-1 den Wert der Funktion F2(n,k); in sehr vielen Fällen bestimmen sie auch den Wert von F3(n,k); ferner geben sie auch extreme Graphen an. Für den Fall d \geq 3 erhalten sie gute Abschätzungen bezüglich Fd (n,k). Folgender Satz beantwortet ein seit langem bestehendes Problem: Falls ein n Punkte enthaltender Graph Gn keinen Kreis der Länge 4 enthält und je zwei seiner Punkte durch einen Weg der Länge 2 verbunden sind, dann ist n = 2m+1 und Gn besteht aus m Dreiecken, die einen einzigen gemeinsamen Punkt enthalten. Es werden auch mehrere interessante ungelöste Probleme aufgeworfen.
Reviewer: B.Andrásfai
Classif.: * 05C35 Extremal problems (graph theory)
05C38 Paths and cycles
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag