Zentralblatt MATH

Publications of (and about) Paul Erdös
Zbl.No:  194.25304
Autor:  Erdös, Pál; Rogers, C.A.
Title:  The construction of certain graphs (In English)
Source:  Can. J. Math. 14, 702-707 (1962).
Review:  Ein Graph heiße k-vollständig (k-unvollständig), wenn er einen (keinen) vollständigen Graphen mit k Ecken als Teilgraphen enthält. Hauptergebnis der Note ist (vgl. 3. Theorem, S. 704), daß sich zu je zwei natürlichen Zahlen k und l (k \geq 3) stets ein Graph G mit weniger als l1+ck Ecken so finden läßt, daß G k-unvollständig und jeder von l Ecken aufgespannte Untergraph von G (k-1)-vollständig ist. Hierbei können die positiven Konstanten ck (k \geq 3) so gewählt werden, daß ck ~ 1/(512 k4 log k) mit k ––> oo gilt. Der erste Autor hatte in einer früheren Note für f(k,l) (l = kleinste natürliche Zahl mit der Eigenschaft, daß für jeden Graphen G mit f(k,l) Ecken entweder G k-vollständig oder der komplementäre Graph zu G l-vollständig ist, vgl. den Satz von Ramsey) die untere Schranke l1+c3 < f(3,l) \leq f(k,l), (k \geq 4) ermittelt. Aus dem neuen Ergebnis folgt jetzt sogar: l1+ck < h(k,l) \leq f(k,l) für k \geq 3, worin h(k,l) die kleinste natürliche Zahl mit der Eigenschaft bedeutet, daß jeder Graph G mit h(k,l) Ecken entweder k-vollständig ist oder l Ecken in G existieren, so daß der von diesen Ecken aufgespannte Untergraph von G (k-1)-unvollständig ist.
Reviewer:  K.Wagner
Classif.:  * 05C55 Generalized Ramsey theory
                   05C35 Extremal problems (graph theory)
Index Words:  topology

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page