An upper bound on the number of cliques in a graph
Authors:
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.Keywords
This publication has 9 references indexed in Scilit:
- On graphs with polynomially solvable maximum‐weight clique problemNetworks, 1989
- On diameters and radii of bridged graphsDiscrete Mathematics, 1989
- A Note on Independent Sets in TreesSIAM Journal on Discrete Mathematics, 1988
- The number of maximal independent sets in a connected graphDiscrete Mathematics, 1988
- The number of maximal independent sets in connected graphsJournal of Graph Theory, 1987
- The Number of Maximal Independent Sets in a TreeSIAM Journal on Algebraic Discrete Methods, 1986
- The maximum number of cliques in dense graphsDiscrete Mathematics, 1985
- Über iterierte Clique-GraphenAbhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 1973
- On cliques in graphsIsrael Journal of Mathematics, 1965