AN UPPER BOUND ON THE NUMBER OF CLIQUES IN A GRAPH

Authors
FARBER M HUJTER M TUZA Z
Citation
M. Farber et al., AN UPPER BOUND ON THE NUMBER OF CLIQUES IN A GRAPH, Networks, 23(3), 1993, pp. 207-210
Citations number
10
Categorie Soggetti
Mathematics,"Computer Sciences","Computer Applications & Cybernetics
Journal title
Networks → ACNP
ISSN journal
00283045
Volume
23
Issue
3
Year of publication
1993
Pages
207 - 210
Database
ISI
SICI code
0028-3045(1993)23:3<207:AUBOTN>2.0.ZU;2-Z
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 ve rtices contains no set of t + 1 pairwise disjoint edges as an induced subgraph, then G has fewer than (n/2t)2t maximal complete subgraphs.