Premium
Vertices of given degree in series‐parallel graphs
Author(s) -
Drmota Michael,
Giménez Omer,
Noy Marc
Publication year - 2010
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20290
Subject(s) - degree (music) , mathematics , series (stratigraphy) , central limit theorem , limit (mathematics) , exponential function , combinatorics , quadratic equation , discrete mathematics , singularity , multivariate statistics , statistics , mathematical analysis , paleontology , physics , geometry , acoustics , biology
Abstract We show that the numbers of vertices of a given degree k ≥ 1 in several kinds of series‐parallel labeled graphs of size n satisfy a central limit theorem with mean and variance proportional to n , and quadratic exponential tail estimates. We further prove a corresponding theorem for the number of nodes of degree two in labeled planar graphs. The proof method is based on generating functions and singularity analysis. In particular, we need systems of equations for multivariate generating functions and transfer results for singular representations of analytic functions. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010