Clique numbers of graphs
- authored by
- Paul Erdös, Marcel Erné
- Abstract
For each natural number n, denote by G(n) the set of all numbers c such that there exists a graph with exactly c cliques (i.e., complete subgraphs) and n vertices. We prove the asymptotic estimate |G(n)| = 0(2n · n-2/5) and show that all natural numbers between n + 1 and 2n-6n5/6 belong to G(n). Thus we obtain lim n→∞ |G(n)| 2n=0, while lim n→∞ |G(n)| an= ∞ for all 0 < a < 2.
- Organisation(s)
-
Institute of Algebra, Number Theory and Discrete Mathematics
- External Organisation(s)
-
Hungarian Academy of Sciences
- Type
- Article
- Journal
- Discrete mathematics
- Volume
- 59
- Pages
- 235-242
- No. of pages
- 8
- ISSN
- 0012-365X
- Publication date
- 05.1986
- Publication status
- Published
- Peer reviewed
- Yes
- ASJC Scopus subject areas
- Theoretical Computer Science, Discrete Mathematics and Combinatorics
- Electronic version(s)
-
https://doi.org/10.1016/0012-365X(86)90170-6 (Access:
Open)
