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
    Just a short side note: A random $k$-regular graph will be not only very well connected, but remarkably will have the best connectivity possible. Random $k$-regular graphs with high probability are more "well connected" than any known constructions, and are as well connected as possible. This is a very deep theorem in Spectral Graph Theory. It is the Alon Conjecture which was resolved by Joel Friedmann in 2003. The proof is about 110 pages. If you like I could be more precise and elaborate on the above.2011-09-18
  • 0
    @Eric since random $k$-regular graphs are good expanders, it makes sense that they are VERY WELL connected. But I was wondering if there was a general bound or expression for the average $r$ in terms of $k$ and $n$. I could expand my question to clarify this. I would definitely like an explanation of "as well connected as possible" that doesn't require me to read a 110 page paper ;).2011-09-18
  • 0
    I take it we're assuming $k$ is at least $3$?2011-09-18
  • 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