Name
Abstract | ||
|---|---|---|
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 Gn;p with p logn=n for any constant <2=3. On the other hand, this is not true for somewhat higher densities: If p (logn)3=(n log logn )w ith >1= 8t hen with high probability we need to delete more edges than one from every triangle. |
Year | Venue | Keywords |
|---|---|---|
2000 | Electronic Journal of Combinatorics | cover graph,poset proposed running head: sparse cover graphs,our result has a natural algorithmic interpretation. keywords: random graph |
Field | DocType | Volume |
Block graph,Random regular graph,Discrete mathematics,Combinatorics,Line graph,Random graph,Forbidden graph characterization,Universal graph,Mathematics,Planar graph,Complement graph | Journal | 7 |
Citations | PageRank | References |
3 | 0.41 | 3 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tom Bohman | 1 | 250 | 33.01 |
| Alan M. Frieze | 2 | 4837 | 787.00 |
| M. Ruszinkó | 3 | 230 | 35.16 |
| Lubos Thoma | 4 | 42 | 5.34 |