Abstract | ||
---|---|---|
In this paper we establish the cover time of a random graph G(d) chosen uniformly at random from the set of graphs with vertex set [n] and degree sequence d. We show that under certain restrictions on d, the cover time of G(d) is whp asymptotic to d−1d−2θdnlogn. Here θ is the average degree and d is the effective minimum degree. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1016/j.disc.2012.07.006 | Discrete Mathematics |
Keywords | Field | DocType |
Cover time,Random graphs,Degree sequence | Discrete mathematics,Random regular graph,Combinatorics,Random graph,Edge cover,Bipartite graph,Frequency partition of a graph,Degree (graph theory),Vertex cover,Mathematics,Maximal independent set | Journal |
Volume | Issue | ISSN |
312 | 21 | 0012-365X |
Citations | PageRank | References |
6 | 0.72 | 6 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mohammed Abdullah | 1 | 6 | 0.72 |
Colin Cooper | 2 | 857 | 91.88 |
Alan M. Frieze | 3 | 4837 | 787.00 |