Name
Abstract | ||
|---|---|---|
AbstractLet K4- denote the diamond graph, formed by removing an edge from the complete graph K4. We consider the following random graph process: starting with n isolated vertices, add edges uniformly at random provided no such edge creates a copy of K4-. We show that, with probability tending to 1 as nï ∞, the final size of the graph produced is ï logï nï n3/2. Our analysis also suggests that the graph produced after i edges are added resembles the uniform random graph, with the additional condition that the edges which do not lie on triangles form a random-looking subgraph. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 513-551, 2014 |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1002/rsa.20517 | Periodicals |
Keywords | Field | DocType |
H-free process,random greedy algorithm,differential equations method | Discrete mathematics,Strength of a graph,Combinatorics,Line graph,Diamond graph,Cycle graph,Null graph,Butterfly graph,Multiple edges,Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
45 | 3 | 1042-9832 |
Citations | PageRank | References |
3 | 0.47 | 7 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael E. Picollelli | 1 | 10 | 2.56 |