Loading [MathJax]/jax/output/HTML-CSS/jax.js

Veronika Kraus - The degree distribution in unlabelled 2-connected graph families

dmtcs:2773 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - https://doi.org/10.46298/dmtcs.2773
The degree distribution in unlabelled 2-connected graph familiesArticle

Authors: Veronika Kraus 1

  • 1 Institut für Diskrete Mathematik und Geometrie [Wien]

We study the random variable Xkn, counting the number of vertices of degree k in a randomly chosen 2-connected graph of given families. We prove a central limit theorem for Xkn with expected value EXknμkn and variance VXknσ2kn, both asymptotically linear in n, for both rooted and unrooted unlabelled 2-connected outerplanar or series-parallel graphs.


Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: unlabelled graphs,cycle index sums,central limit law,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

1 Document citing this article

Consultation statistics

This page has been seen 253 times.
This article's PDF has been downloaded 281 times.