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

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