Skip to Main content Skip to Navigation
Conference papers

The degree distribution in unlabelled $2$-connected graph families

Abstract : We study the random variable $X_n^k$, 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 $X_n^k$ with expected value $\mathbb{E}X_n^k \sim \mu_kn$ and variance $\mathbb{V}X_n^k \sim \sigma_k^2n$, both asymptotically linear in $n$, for both rooted and unrooted unlabelled $2$-connected outerplanar or series-parallel graphs.
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185571
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 4:32:25 PM
Last modification on : Tuesday, March 7, 2017 - 3:07:08 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:48:20 AM

File

dmAM0132.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01185571, version 1

Collections

Citation

Veronika Kraus. The degree distribution in unlabelled $2$-connected graph families. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. pp.453-472. ⟨hal-01185571⟩

Share

Metrics

Record views

178

Files downloads

521