DMTCS Proceedings, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)

Font Size:  Small  Medium  Large

The degree distribution in unlabelled 2-connected graph families

Veronika Kraus

Abstract


We study the random variable Xnk, 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 Xnk with expected value EXnk ∼µkn and variance VXnk∼σk2n, both asymptotically linear in n, for both rooted and unrooted unlabelled 2-connected outerplanar or series-parallel graphs.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional