Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 187.21004
Autor: Erdös, Pál; Moser, L.
Title: An extremal problem in graph theory (In English)
Source: J. Aust. Math. Soc. 11, 42-47 (1970).
Review: G(n; l) sei ein Graph mit n Knotenpunkten und l Kanten. f0(n,k) sei die kleinste Zahl, so daß ein G(n; f0(n,k)) existiert, für welches zu je k Knotenpunkten x1,...,xk ein weiterer Knotenpunkt y existiert, der mit allen Punkten xi, i = 1,...,k, durch eine Kante verbunden ist. Wir zeigen: für jedes n > k gilt f(n,k) = (k-1)n-\binom{k}{2}+[\frac{n-k}{2}]+1. Die extremalen Graphen werden auch bestimmt, und verschiedene zum Teil ungelöste Probleme werden diskutiert.
Classif.: * 05C35 Extremal problems (graph theory)
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag