Spelling suggestions: "subject:"combinatorics : random : planar : graph"" "subject:"combinatiorics : random : planar : graph""
1 |
Uniform random planar graphs with degree constraintsDowden, Christopher Thomas January 2008 (has links)
Random planar graphs have been the subject of much recent work. Many basic properties of the standard uniform random planar graph $P_{n}$, by which we mean a graph chosen uniformly at random from the set of all planar graphs with vertex set $ { 1,2, ldots, n }$, are now known, and variations on this standard random graph are also attracting interest. Prominent among the work on $P_{n}$ have been asymptotic results for the probability that $P_{n}$ will be connected or contain given components/ subgraphs. Such progress has been achieved through a combination of counting arguments cite{mcd} and a generating function approach cite{gim}. More recently, attention has turned to $P_{n,m}$, the graph taken uniformly at random from the set of all planar graphs on ${ 1,2, ldots, n }$ with exactly $m(n)$ edges (this can be thought of as a uniform random planar graph with a constraint on the average degree). In cite{ger} and cite{gim}, the case when $m(n) =~!lfloor qn floor$ for fixed $q in (1,3)$ has been investigated, and results obtained for the events that $P_{n, lfloor qn floor}$ will be connected and that $P_{n, lfloor qn floor}$ will contain given subgraphs. In Part I of this thesis, we use elementary counting arguments to extend the current knowledge of $P_{n,m}$. We investigate the probability that $P_{n,m}$ will contain given components, the probability that $P_{n,m}$ will contain given subgraphs, and the probability that $P_{n,m}$ will be connected, all for general $m(n)$, and show that there is different behaviour depending on which `region' the ratio $rac{m(n)}{n}$ falls into. In Part II, we investigate the same three topics for a uniform random planar graph with constraints on the maximum and minimum degrees.
|
Page generated in 0.0828 seconds