Details
| Originalsprache | Englisch |
|---|---|
| Seiten (von - bis) | 235-242 |
| Seitenumfang | 8 |
| Fachzeitschrift | Discrete mathematics |
| Jahrgang | 59 |
| Ausgabenummer | 3 |
| Publikationsstatus | Veröffentlicht - Mai 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 Sachgebiete
- Mathematik (insg.)
- Theoretische Informatik
- Mathematik (insg.)
- Diskrete Mathematik und Kombinatorik
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
in: Discrete mathematics, Jahrgang 59, Nr. 3, 05.1986, S. 235-242.
Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › 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 -