Abstract | ||
---|---|---|
Let G3-out denote the random graph on vertex set [n] in which each vertex chooses three neighbors uniformly at random. Note that G3-out has minimum degree 3 and average degree 6. We prove that the probability that G3-out is Hamiltonian goes to 1 as n tends to infinity. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 |
Year | DOI | Venue |
---|---|---|
2009 | 10.1002/rsa.v35:4 | Random Struct. Algorithms |
Keywords | Field | DocType |
random graphs,random graph,hamilton cycle | Discrete mathematics,Random regular graph,Combinatorics,Random graph,Vertex (geometry),Hamiltonian (quantum mechanics),struct,Infinity,Degree (graph theory),Mathematics | Journal |
Volume | Issue | ISSN |
35 | 4 | 1042-9832 |
Citations | PageRank | References |
11 | 0.81 | 11 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tom Bohman | 1 | 250 | 33.01 |
Alan M. Frieze | 2 | 4837 | 787.00 |