2006 | OriginalPaper | Chapter
Random Graphs from Planar and Other Addable Classes
Authors: Colin McDiarmid, Angelika Steger, Dominic J. A. Welsh
Publisher: Springer Berlin Heidelberg
We study various properties of a random graph
R
n
, drawn uniformly at random from the class
$$ \mathcal{A}_n $$
of all simple graphs on
n
labelled vertices that satisfy some given property, such as being planar or having tree-width at most κ. In particular, we show that if the class
$$ \mathcal{A} $$
is’ small’ and ‘addable’, then the probability that
R
n
is connected is bounded away from 0 and from 1. As well as connectivity we study the appearances of subgraphs, and thus also vertex degrees and the numbers of automorphisms. We see further that if
$$ \mathcal{A} $$
is’ smooth’ then we can make much more precise statements for example concerning connectivity.
