Abstract
The edges of the random graph (with the edge probability p=1/2) can be covered using O(n 2 lnln n/(ln n) 2 ) cliques. Hence this is an upper bound on the intersection number (also called clique cover number) of the random graph. A lower bound, obtained by counting arguments, is (1-e{open})n 2 /(2lg n) 2 .
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1-5 |
| Number of pages | 5 |
| Journal | Combinatorica |
| Volume | 13 |
| Issue number | 1 |
| DOIs | |
| State | Published - Mar 1993 |
Keywords
- AMS subject classification code (1991): 05C80
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Computational Mathematics
Fingerprint Dive into the research topics of 'Clique coverings of the edges of a random graph'. Together they form a unique fingerprint.
Cite this
Bollobás, B., Erdos, P., Spencer, J., & West, D. B. (1993). Clique coverings of the edges of a random graph. Combinatorica, 13(1), 1-5. https://doi.org/10.1007/BF01202786