Abstract | ||
---|---|---|
For a fixed integer g≥0, let Sg(n,m) be a graph chosen uniformly at random from all graphs with n vertices and m edges that are embeddable on the orientable surface Sg of genus g. We prove that the component structure of Sg(n, m) features two phase transitions. The first one is analogous to the emergence of the giant component in the classical Erdős-Rényi random graph G(n, m) at m∼n2 second phase transition occurs at m∼n, when the giant component covers almost all vertices. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1016/j.endm.2017.07.024 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Random graphs,surface,phase transition,giant component | Integer,Discrete mathematics,Graph,Random regular graph,Combinatorics,Random graph,Vertex (geometry),Phase transition,Giant component,Mathematics | Journal |
Volume | ISSN | Citations |
61 | 1571-0653 | 0 |
PageRank | References | Authors |
0.34 | 3 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mihyun Kang | 1 | 163 | 29.18 |
Michael Moßhammer | 2 | 0 | 0.34 |
Philipp Sprüssel | 3 | 46 | 8.52 |