I need to be able to generate random graphs (both general and bipartite). I require that the generated graph have a specified number of vertices and edges (in the bipartite case the number of vertices on each side is specified). My particular problem is that I also require that the graph be connected. I have found no research on this problem. Generating all graphs satisfying specifications and then selected from this set at random is not feasible for space reasons (I also don't know how to do this).

My plan is to generate a graph at random keeping track of the number of components until I only have d edges to add and the generated graph so far has (d + 1) components. Then add the remaining edges ensureing that each edge added joins two unconnected components of the graph. The difficulty is that now each time I generate a new edge at random I must discard it if both of its endpoints are on the same component of the graph. I have no idea how many edges I can be expected to discard by this approach and have not found anything in the literature on my approach or any other approach.

Is there a result that states how many edges I need to generate before the graph becomes connected?

Is there another approach that guarentees termination in a reasonable time (O(nlog n) or better)?

I rarely visit here so emailing me at rpboland@gmail.com might be useful.

0