Geodesic
A note on sparse random graphs and cover graphs
The electronic journal of combinatorics, Tome 7 (2000)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
It is shown in this note that with high probability it is enough to destroy all triangles in order to get a cover graph from a random graph $G_{n,p}$ with $p\le \kappa \log n/n$ for any constant $\kappa < 2/3$. On the other hand, this is not true for somewhat higher densities: If $p\ge \lambda (\log n)^3 / (n\log\log n)$ with $\lambda > 1/8$ then with high probability we need to delete more edges than one from every triangle. Our result has a natural algorithmic interpretation.
DOI : 10.37236/1497
Classification : 05C80
Mots-clés : poset, cover graph, random graph 
Tom Bohman; Alan Frieze; Miklós Ruszinkó; Lubos Thoma. A note on sparse random graphs and cover graphs. The electronic journal of combinatorics, Tome 7 (2000). doi: 10.37236/1497
@article{10_37236_1497,
     author = {Tom Bohman and Alan Frieze and Mikl\'os Ruszink\'o and Lubos Thoma},
     title = {A note on sparse random graphs and cover graphs},
     journal = {The electronic journal of combinatorics},
     year = {2000},
     volume = {7},
     doi = {10.37236/1497},
     zbl = {0939.05072},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1497/}
}
TY  - JOUR
AU  - Tom Bohman
AU  - Alan Frieze
AU  - Miklós Ruszinkó
AU  - Lubos Thoma
TI  - A note on sparse random graphs and cover graphs
JO  - The electronic journal of combinatorics
PY  - 2000
VL  - 7
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1497/
DO  - 10.37236/1497
ID  - 10_37236_1497
ER  - 
%0 Journal Article
%A Tom Bohman
%A Alan Frieze
%A Miklós Ruszinkó
%A Lubos Thoma
%T A note on sparse random graphs and cover graphs
%J The electronic journal of combinatorics
%D 2000
%V 7
%U http://geodesic.mathdoc.fr/articles/10.37236/1497/
%R 10.37236/1497
%F 10_37236_1497

Cité par Sources :