Department of Mathematics, Royal Holloway
2:30pm Tuesday, 28th of July, 2009
Room 5.02, Informatics Forum
Given a graph $G=(V,E)$ on $V=\{1,\ldots,n\}$ and two edges $e=ab, f=cd \in E$, the edges $e$ and $f$ are $\emph{pegged}$ if two vertices $e'=n+1$ and $f'=n+2$ are added to $V$, the edges $e$ and $f$ are deleted, and the edges $\ a e'$, $be'$, $cf'$, $df'$ and $e'f'$ are added. In other words, the edges $e$ and $f$ are subdivided and a new edge is introduced between the two new vertices. Note that if any two edges of a $3$-regular graph are pegged, then another $3$-regular graph results.
In this talk we consider the following (random) pegging process $\scrP(G_0)$: Start with a fixed graph $G_0$. Usually, but not always, $G_0$ is 3-regular and connected. At each step $t\ge 1$, choose two edges uniformly at random from all edges of $G_{t-1}$ and peg them to obtain $G_{t}$. Let $n_t$ denote the number of vertices of $G_t$, so that $n_t=n_0+2t$.
We show that asymptotically almost surely (a.a.s., that is, with probability tending to one as $t$ tends to infinity) the diameter of $G_{t}$ is at most $C \log t$, where $C$ is a constant depending on $G_0$. This is joint work with Angelika Steger and Nicholas Wormald.