0

I want to find an algorithm to generate an undirected graph with a given size and a given connectivity, where each vertex has exactly the specified number of edges coming from it. The closest thing I've found so far is this:

Random simple connected graph generation with given sparseness

The difference here being that I'm less interested in the total number of edges in the graph (though that can easily be computed too) -- what I'm looking for is a guarantee that each vertex has exactly the given number of connections.

For example:

Input: Size - 6   Connectivity - 4
Output: Undirected graph with 6 verteces and (6*4/2)=12 edges, where each vertex has 4 connnections.

I am assuming that my inputs will have a valid output.

Community
  • 1
  • 1
growling_egg
  • 307
  • 1
  • 9
  • This might help, and may in fact be a duplicate: http://stackoverflow.com/questions/23761401/how-to-create-a-symmetric-matrix-of-1s-and-0s-with-constant-row-and-column-sum – beaker Feb 13 '17 at 22:29
  • I didn't know that a graph where all nodes have the same number of neighbors was called a "regular graph." That gives me a lot of new places to research. Thanks for your help! I'll come back and post a definitive answer if I can come up with one. – growling_egg Feb 14 '17 at 03:23
  • The accepted answer in the question I linked contains an algorithm to generate random graphs of this type. The only thing you really need to play around with is how many times to swap edges. – beaker Feb 14 '17 at 15:53

0 Answers0