Name
Abstract | ||
|---|---|---|
Let be a class of labeled connected graphs and let be the class of biconnected graphs in . In this paper we develop a general framework that allows us to derive mechanically the degree distribution of random graphs with nvertices from certain 'nice' classes as a function of the degree distribution of the graphs in that are drawn under a specific probabilistic model, namely the Boltzmann model. We apply this framework to obtain the degree distribution of a random outerplanar graph and a random series-parallel graph. For the latter we formulate a generic concentration result that allows us to make statements that are true with high probability for a large family of variables defined on random graphs drawn according to the Boltzmann distribution. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-85363-3_25 | APPROX-RANDOM |
Keywords | Field | DocType |
random graph,series-parallel graphs,degree distribution,degree sequences,biconnected graph,general framework,boltzmann model,random series-parallel graph,random outerplanar,specific probabilistic model,random outerplanar graph,generic concentration result,boltzmann distribution,planar graph,outerplanar graph,degree sequence,uniform distribution,probability theory,analytic combinatorics | Discrete mathematics,Random regular graph,Outerplanar graph,Combinatorics,Indifference graph,Random graph,Partial k-tree,Chordal graph,Degree distribution,Pathwidth,Mathematics | Conference |
Volume | ISSN | Citations |
5171 | 0302-9743 | 3 |
PageRank | References | Authors |
0.52 | 11 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicla Bernasconi | 1 | 18 | 2.40 |
| Konstantinos Panagiotou | 2 | 290 | 27.80 |
| Angelika Steger | 3 | 995 | 111.50 |