Abstract | ||
---|---|---|
In this work we determine the expected number of vertices of degree k = k(n) in a graph with n vertices that is drawn uniformly at random from a subcritical graph class. Examples of such classes are outerplanar, series-parallel, cactus and clique graphs. Moreover, we provide exponentially small bounds for the probability that the quantities in question deviate from their expected values. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1017/S0963548309990368 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
random graph,degree sequence,n vertex,expected number,subcritical class,question deviate,expected value,degree k,subcritical graph class,exponentially small bound,clique graph,series parallel | Discrete mathematics,Random regular graph,Block graph,Outerplanar graph,Combinatorics,Random graph,Chordal graph,Cycle graph,Independent set,Mathematics,Split graph | Journal |
Volume | Issue | ISSN |
18 | 5 | 0963-5483 |
Citations | PageRank | References |
14 | 0.92 | 9 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Nicla Bernasconi | 1 | 18 | 2.40 |
Konstantinos Panagiotou | 2 | 290 | 27.80 |
Angelika Steger | 3 | 995 | 111.50 |