| Description |
A graph is $r$-regular if all its vertices have the same degree $r$. A random $r$-regular graph with $n$ vertices is a graph sampled uniformly at random from the set of all $r$-regular graphs on $n$ vertices. There are various sampling methods for this. In this talk we look at one of them: The Configuration Model. We then look at the cover time of a random walk on such a graph, which roughly speaking, is the time taken (in expectation) by the walk to visit all the vertices. This cover time calculation, due to Colin Cooper and Alan Frieze, uses generating function technique and results from complex analysis, which we illustrate in this talk.
(Key words.) Random regular graphs, configuration model, cover time, combinatorics.
|