Vertices of given degree in series‐parallel graphs |
| |
| Authors: | Michael Drmota Omer Giménez Marc Noy |
| |
| Institution: | 1. TU Wien Department of Discrete Mathematics and Geometry, Technische Universit?t Wien, A1040 Wien, Austria;2. Departament de Llenguatges I Sistemes Informàtics, Universitat Politècnica de Catalunya, 08034 Barcelona, Spain;3. Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, 08034 Barcelona, Spain |
| |
| 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 |
| |
| Keywords: | series‐parallel graphs degree distribution generating functions singularity analysis central limit theorem |
|
|
