Journal article icon

Journal article

On the Maximum Degree of a Random Planar Graph.

Abstract:
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:
Published

Actions


Access Document


Publisher copy:
10.1017/S0963548308009097

Authors


McDiarmid, C More by this author
Journal:
Combinatorics, Probability and Computing
Volume:
17
Issue:
4
Pages:
591-601
Publication date:
2008
DOI:
EISSN:
1469-2163
ISSN:
0963-5483
URN:
uuid:5f097513-a439-4815-bdb5-e147feeb7b02
Source identifiers:
102285
Local pid:
pubs:102285
Language:
English

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP