3
$\begingroup$

If you take a random $k$-regular graph, with high probability (tending to 1 as the size of the graph grows) almost all of the nodes will be in one giant connected component. How well connected is this component? How many edges will I have to remove in order to disconnect this graph?

This is motivated by an application where I generate a random connected $k$-regular graphs and then remove $r$ many random spanning trees. The concern: how large can $r$ be (on average) for a $k$-regular graph on $n$ vertices?

  • 0
    @ChrisEagle yeah, definitely. I will wait a bit longer to see if there is any other confusion about my question and then edit the remarks in, and maybe some random thoughts related to expander graphs (although I am interested in the question as stated, not the Cheeger constant).2011-09-18

0 Answers 0