On the Maximum Degree of a Random Planar Graph.
- Let the random graph Rn be drawn uniformly at random from the set of all simple planar graphs on n labelled vertices. We see that with high probability the maximum degree of Rn is ⊖(ln n). We consider also the maximum size of a face and the maximum increase in the number of components on deleting a vertex. These results extend to graphs embeddable on any fixed surface. © 2008 Cambridge University Press.
- Publication status:
- Publisher copy:
- Copyright date:
Views and Downloads
If you are the owner of this record, you can report an update to it here: Report update to this record