Details
| Original language | English |
|---|---|
| Pages (from-to) | 235-242 |
| Number of pages | 8 |
| Journal | Discrete mathematics |
| Volume | 59 |
| Issue number | 3 |
| Publication status | Published - May 1986 |
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.
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Mathematics(all)
- Discrete Mathematics and Combinatorics
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Discrete mathematics, Vol. 59, No. 3, 05.1986, p. 235-242.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Clique numbers of graphs
AU - Erdös, Paul
AU - Erné, Marcel
PY - 1986/5
Y1 - 1986/5
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=24844464547&partnerID=8YFLogxK
U2 - 10.1016/0012-365X(86)90170-6
DO - 10.1016/0012-365X(86)90170-6
M3 - Article
AN - SCOPUS:24844464547
VL - 59
SP - 235
EP - 242
JO - Discrete mathematics
JF - Discrete mathematics
SN - 0012-365X
IS - 3
ER -