Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-24T22:49:32.820Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Maximum Degree of a Random Planar Graph

Published online by Cambridge University Press:  01 July 2008

COLIN McDIARMID  and
BRUCE REED
COLIN McDIARMID
Affiliation:
Department of Statistics, University of Oxford, UK (e-mail: [email protected])
BRUCE REED
Affiliation:
Canada Research Chair in Graph Theory, Department of Computer Science, McGill University, Montreal, Canada and Laboratoire I3S, CNRS Sophia-Antipolis, France (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

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.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 4 , July 2008 , pp. 591 - 601
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bender, E., Gao, Z. and Wormald, N. (2002) The number of labeled 2-connected planar graphs. Electron. J. Combin. 9 # 43.CrossRefGoogle Scholar
[2]Bollobás, B. (2001) Random Graphs, 2nd edn, Vol. 73 of Cambridge Studies in Advanced Mathematics, Cambridge University Press.Google Scholar
[3]Gao, Z. and Wormald, N. (2000) The distribution of the maximum vertex degree in random planar maps. J. Combin. Theory Ser. A 89 201–230.CrossRefGoogle Scholar
[4]Gerke, S., McDiarmid, C., Steger, A. and Weissl, A. (2005) Random planar graphs with n nodes and a fixed number of edges. In Proc. ACM–SIAM Symposium on Discrete Algorithms (SODA), pp. 999–1007.Google Scholar
[5]Gerke, S., McDiarmid, C., Steger, A. and Weissl, A. (2007) Random planar graphs with a given average degree. In Combinatorics, Complexity and Chance: A Tribute to Dominic Welsh (Grimmett, G. and McDiarmid, C., eds), Oxford University Press, pp. 83–102.CrossRefGoogle Scholar
[6]Giménez, O. and Noy, M. (2005) Asymptotic enumeration and limit laws of planar graphs. arXiv: math.CO/0501269.Google Scholar
[7]Luczak, M., McDiarmid, C., and Upfal, E. (2003) On-line routing of random calls in networks. Probab. Theory Rel. Fields 125 457–482.CrossRefGoogle Scholar
[8]McDiarmid, C. (2006) Random graphs on surfaces. Preprint 722, November 2006, Centre de Recerca Matemàtica, Barcelona (http://www.crm.es/)Google Scholar
[9]McDiarmid, C., Steger, A. and Welsh, D. (2005) Random planar graphs. J. Combin. Theory Ser. B 93 187–205.CrossRefGoogle Scholar
[10]McDiarmid, C., Steger, A. and Welsh, D. (2006) Random graphs from planar and other addable classes. In Topics in Discrete Mathematics (Klazar, M., Kratochvil, J., Loebl, M., Matoušek, J., Thomas, R. and Valtr, P., eds), Vol. 26 of Algorithms and Combinatorics, Springer, pp. 231–246.CrossRefGoogle Scholar
[11]Mohar, B. and Thomassen, C. (2001) Graphs on Surfaces, The Johns Hopkins University Press.CrossRefGoogle Scholar
[12]Whitney, H. (1932) Congruent graphs and the connectivity of graphs. Amer. J. Math. 54 150–168.CrossRefGoogle Scholar