Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-15T14:38:26.902Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Minimum Number of k-Cliques in Graphs with Restricted Independence Number

Published online by Cambridge University Press:  02 October 2001

V. NIKIFOROV
V. NIKIFOROV
Affiliation:
Beli brezi bl. 2, Sofia 1680, Bulgaria (e-mail: vladon@otel.net)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We investigate the following problem of Erdős:

Determine the minimum number of k-cliques in a graph of order n with independence number [ges ] l.

We disprove the original conjecture of Erdős which was stated in 1962 for all but a finite number of pairs k, l, and give asymptotic estimates for l = 3, k [ges ] 4, and l = 4, k [ges ] 4.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 10 , Issue 4 , July 2001, pp. 361 - 366
Copyright
2001 Cambridge University Press