Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 116.01202
Autor: Erdös, Pál
Title: On the number of complete subgraphs contained in certain graphs (In English)
Source: Publ. Math. Inst. Hung. Acad. Sci., Ser. A 7, 459-464 (1962).
Review: Let G and \bar G (the "complement" of G) be graphs with the same vertices and without loops or multiple edges, such that every two distinct vertices are joined by an edge in exactly one of these graphs. Ck (G) is the number of complete subgraphs of G with k vertices. Theorem 1 states that for every k \geq 3 and every n, there exists a G with n vertices such that Ck (G)+Ck (\bar G) < {n \choose k} 21-{k \choose 2}. Theorem 2 and 3 determine the maximum value of Ck (G) as G runs over (in the case of Theorem 2) all graphs with l edges and (in Theorem 3) all graphs with n vertices which do not posses a complete subgraph with l vertices. Some unsolved related problems are mentioned.
Reviewer: C.St.J.A.Nash-Williams
Classif.: * 05C30 Enumeration of graphs and maps
Index Words: combinatorics
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag