Geodesic
A note on sparse random graphs and cover graphs
The electronic journal of combinatorics, Tome 7 (2000)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 
@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
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

Cité par Sources :