×

zbMATH — the first resource for mathematics

On the number of complete subgraphs contained in certain graphs. (English) Zbl 0116.01202
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. \(C_k (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 \(C_k (G)+C_k (\bar G) < {n \choose k} 2^{1-{k \choose 2}}\). Theorem 2 and 3 determine the maximum value of \(C_k (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 possess a complete subgraph with \(l\) vertices. Some unsolved related problems are mentioned.

MSC:
05C30 Enumeration in graph theory
Keywords:
combinatorics
PDF BibTeX XML Cite