Carregant...
Carregant...

Vés al contingut (premeu Retorn)

The maximum degree of random planar graphs

Autor
Drmota, M.; Giménez, O.; Noy, M.; Panagiotou, K.; Steger, A.
Tipus d'activitat
Article en revista
Revista
Proceedings of the London Mathematical Society
Data de publicació
2014-10-01
Volum
109
Pàgina inicial
892
Pàgina final
920
DOI
https://doi.org/10.1112/plms/pdu024 Obrir en finestra nova
URL
http://plms.oxfordjournals.org/content/109/4/892 Obrir en finestra nova
Resum
McDiarmid and Reed ['On the maximum degree of a random planar graph', Combin. Probab. Comput. 17 (2008) 591-601] showed that the maximum degree of a random labeled planar graph with vertices satisfies with high probability (w.h.p.)for suitable constants . In this paper, we determine the precise asymptotics, showing in particular that w.h.p. for a constant that we determine explicitly. The proof combines tools from analytic combinatorics and Boltzmann sampling techniques.
Paraules clau
ASYMPTOTIC ENUMERATION, BOLTZMANN SAMPLERS, SERIES-PARALLEL GRAPHS
Grup de recerca
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants

  • Drmota, Michael  (autor)
  • Giménez, Omer  (autor)
  • Noy Serrano, Marcos  (autor)
  • Panagiotou, K  (autor)
  • Steger, A  (autor)