Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 177.52502
Autor: Erdös, Pál
Title: On the number of complete subgraphs and circuits contained in graphs (In English)
Source: Cas. Pestováni Mat. 94, 290-296 (1969).
Review: Let G(n; k) be a graph of n vertices and k edges. Kp denotes a complete graph of p vertices. Let n \equiv r (mod p-1), m(n; p = {p-2 \over 2(p-1)} (n2-r2)+{r \choose 2}, 0 \leq r \leq p-1. A well known theorem of Turán states that every G(n; m(n; p)+1) contains a Kp and that this result is best possible. Denote by fn(p; 1) the largest integer so that every G(n; m(n; p)+1) contains at least fn(p; 1) Kp's. The author proves that for n > n0(p) fn(p; 1) = prodi = 0p-1 [{n+1 \over p-1}]. In particular f3n(4,1) = n2. Several further results are proved, fn(p,1) is determined for 1 < \epsilonpn and several unsolved problems are stated. [See also P. Erdös, Illinois J. Math. 6, 122-127 (1962; Zbl 099.39401)]
Classif.: * 05C20 Directed graphs (digraphs)
05C38 Paths and cycles
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag