It was shown that (whp), for $r\ge 3$ the cover time $C_G$ of a random $r$-regular graph $G_r$ is asymptotic to $\theta_r n \ln n$, where $\theta_r=({r-1})/({r-2})$. In this talk we study problems arising from multiple random walks on random regular graphs, and prove the following (whp) results. The time for $k$ independent walks to cover $G_r$ is asymptotic to $ C_G/k$.
For most starting positions, the expected number of steps before any of the walks meet is $\theta_r n/{k\choose 2}$. If the walks can communicate on meeting at a vertex, we show that (for most starting positions) the expected time for $k$ walks to broadcast a single piece of information is asymptotic to $((2 \ln k)/k)\theta_r n$, as $k,n$ tend to infinity.
We also establish properties of walks where particles interact when they meet at a vertex by coalescing or by exploding and destroying each other. As an example, the expected extinction time of $k$ explosive particles ($k$ even) tends to $(2\ln 2) \theta_r n $ as $k$ tends to infinity.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
