Name
Abstract | ||
|---|---|---|
This paper investigates the number of random edges required to add to an arbitrary dense graph in order to make the resulting graph Hamiltonian with high probability. Adding Θ(n) random edges is both necessary and sufficient to ensure this for all such dense graphs. If, however, the original graph contains no large independent set, then many fewer random edges are required. We prove a similar result for directed graphs. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1002/rsa.10070 | Random Struct. Algorithms |
Keywords | Field | DocType |
large independent set,dense graph,similar result,high probability,resulting graph hamiltonian,fewer random edge,arbitrary dense graph,original graph,random edge,independent set | Discrete mathematics,Random regular graph,Combinatorics,Line graph,Random graph,Cycle graph,Mixed graph,Multiple edges,Mathematics,Dense graph,Complement graph | Journal |
Volume | Issue | ISSN |
22 | 1 | Random Structures Algorithms 22(1) (2003), 33--42 |
Citations | PageRank | References |
16 | 1.19 | 3 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tom Bohman | 1 | 250 | 33.01 |
| Alan M. Frieze | 2 | 4837 | 787.00 |
| Ryan Martin | 3 | 144 | 14.43 |