Abstract | ||
---|---|---|
Let c be a constant and (e1,f1),(e2,f2),…,(ecn,fcn) be a sequence of ordered pairs of edges from the complete graph Kn chosen uniformly and independently at random. We prove that there exists a constant c2 such that if c c2, then whp every graph which contains at least one edge from each ordered pair (ei,fi) has a component of size Ω(n), and, if c c2, then whp there is a graph containing at least one edge from each pair that has no component with more than O(n1-ε vertices, where ε is a constant that depends on c2 - c. The constant c2 is roughly 0.97677. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 |
Year | DOI | Venue |
---|---|---|
2006 | 10.1002/rsa.v28:2 | Random Struct. Algorithms |
Keywords | DocType | Volume |
complete graph,wiley periodicals,giant component,constant c2,phase transition,inc. random struct | Journal | 28 |
Issue | ISSN | Citations |
2 | 1042-9832 | 9 |
PageRank | References | Authors |
0.84 | 6 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tom Bohman | 1 | 250 | 33.01 |
Jeong Han Kim | 2 | 699 | 60.19 |