Growing a spanning tree of a graph

Pat Morin

Carleton University

We have a graph $G$ and a special vertex $s\in V(G)$ and grow a spanning tree of $G$, rooted at $s$ by repeatedly selecting a uniformly random edge of $G$ with one vertex in $T$ and one vertex not in $T$ and adding this edge to $T$. After $n-1$ iterations, we get a spanning tree. What is the expected height of this spanning tree? We present results on this problem by relating it to (and solving problems from) first passage percolation theory.

This is joint work with several authors that attended the BIRS Workshop on Random Geometric Graphs and Their Applications to Complex Networks.