On the number of complete subgraphs and circuits contained in graphs. (English) Zbl 0177.52502

Erdős, Pál

Čas. Pěst. Mat. 94, 290-296 (1969).

Let \(G(n;k)\) be a graph of \(n\) vertices and \(k\) edges. \(K_p\) denotes a complete graph of \(p\) vertices. Let \(n \equiv r (\mod p-1)\), \(m(n;p={p-2 \over 2(p-1)} (n^2-r^2)+{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 \(K_p\) and that this result is best possible. Denote by \(f_n(p;1)\) the largest integer so that every \(G(n;m(n;p)+1)\) contains at least \(f_n(p;1)\) \(K_p's\). The author proves that for \(n>n_0(p)\) \[ f_n(p;1) = \prod_{i=0}^{p-1} \left[{n+1 \over p-1}\right]. \] In particular \(f_{3n}(4,1) = n^2\). Several further results are proved, \(f_n(p,1)\) is determined for \(1 < \varepsilon_pn\) and several unsolved problems are stated. [See also P. Erdős, Illinois J. Math. 6, 122-127 (1962; Zbl 0099.39401)]

MSC:

05C20	Directed graphs (digraphs), tournaments
05C38	Paths and cycles

Keywords:

topology

Citations:

Zbl 0099.39401