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.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:491432 |
| Date | January 2008 |
| Creators | Dowden, Christopher Thomas |
| Contributors | McDiarmid, Colin |
| Publisher | University of Oxford |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://ora.ox.ac.uk/objects/uuid:f8a9afe3-30ad-4672-9a6c-4fb9ac9af041 |
Page generated in 0.0251 seconds