Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-08T06:05:08.148Z Has data issue: false hasContentIssue false
  • English
  • Français

The Maximum Degree of Series-Parallel Graphs

Published online by Cambridge University Press:  31 May 2011

MICHAEL DRMOTA ,
OMER GIMÉNEZ  and
MARC NOY
MICHAEL DRMOTA
Affiliation:
Institute of Discrete Mathematics and Geometry, Technische Universität Wien, Wiedner Hauptstrasse 8–10, A–1040 Wien, Austria (e-mail: michael.drmota@tuwien.ac.at)
OMER GIMÉNEZ
Affiliation:
Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, Jordi Girona 1–3, 08034 Barcelona, Spain (e-mail: omer.gimenez@upc.edu)
MARC NOY
Affiliation:
Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Jordi Girona 1–3, 08034 Barcelona, Spain (e-mail: marc.noy@upc.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We prove that the maximum degree Δn of a random series-parallel graph with n vertices satisfies Δn/logn → c in probability, and Δn ~ c logn for a computable constant c > 0. The same kind of result holds for 2-connected series-parallel graphs, for outerplanar graphs, and for 2-connected outerplanar graphs.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 4 , July 2011 , pp. 529 - 570
Copyright
Copyright © Cambridge University Press 2011

References

[1]Bernasconi, N., Panagiotou, K. and Steger, A. (2009) The degree sequence of random graphs from subcritical classes. Combin. Probab. Comput. 18 647–681.CrossRefGoogle Scholar
[2]Bodirsky, M., Giménez, O., Kang, M. and Noy, M. (2007) Enumeration and limit laws for series-parallel graphs. Europ. J. Combin. 8 2091–2105.CrossRefGoogle Scholar
[3]Drmota, M. (1994) A bivariate asymptotic expansion of coefficients of powers of generating functions. Europ. J. Combin. 15 139–152CrossRefGoogle Scholar
[4]Drmota, M. (2009) Random Trees, Springer.CrossRefGoogle Scholar
[5]Drmota, M., Giménez, O. and Noy, M. (2010) Vertices of given degree in series-parallel graphs. Random Struct. Alg. 36 273–314.CrossRefGoogle Scholar
[6]Drmota, M., Giménez, O. and Noy, M. (2011) Degree distribution in random planar graphs. J. Combin. Theory Ser. A 118 2102–2130.CrossRefGoogle Scholar
[7]Drmota, M., Giménez, O. and Noy, M. The maximum degree of planar graphs. Manuscript in preparation.Google Scholar
[8]Flajolet, P. and Odlyzko, A. (1990) Singularity analysis of generating functions. SIAM J. Discrete Math. 3 216–240.CrossRefGoogle Scholar
[9]Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.CrossRefGoogle Scholar
[10]Gao, Z. and Wormald, N. C. (2000) The distribution of the maximum vertex degree in random planar maps. J. Combin. Theory Ser. A 89 201–230.CrossRefGoogle Scholar
[11]Hayman, W. K. (1956) A generalisation of Stirling's formula. J. Reine Angew. Math. 196 67–95.CrossRefGoogle Scholar
[12]McDiarmid, C. and Reed, B. (2008) On the maximum degree of a random planar graph. Combin. Probab. Comput. 17 591–601.CrossRefGoogle Scholar