An upper bound on the number of cliques in a graph
Martin Farber, Mihály Hujter, Źsolt Tuza · Networks · 1993
Abstract Giving a partial solution to a conjecture of Balas and Yu [Networks 19 (1989) 247–235], we prove that if the complement of a graph G on n vertices contains no set of t + 1 pairwise disjoint edges as an induced subgraph, then G has fewer than (n/2t)2t maximal complete subgraphs. © 1993 by John Wiley & Sons, Inc.