MATLAB Answers

Generating all non-isomorphic graphs for a given number of nodes with specified degrees

4 views (last 30 days)
Maxwell Day
Maxwell Day on 24 Nov 2020
Commented: Christine Tobler on 30 Nov 2020
I would like to generate the set of all possible, non-isomorphic graphs for a given number of nodes (n) with specified degrees. Such graphs are relatively small, they may have n = 1-8 where the degree of nodes may range from 1-4.
Generated graphs must be allowed to contain loops and multi-edges. Here, multi-edges have a max value of 2, that is any two nodes may be connected to eachother by a maximum of 2 edges, they may also be connected by 1 edge or 0 edges.
E.G. Generate all possible graphs (thay are allowed to contain loops and multi-edges) with 4 nodes (n = 4) where 2 of the nodes have the degree 2 (2-connected) and two of the nodes have the degree 3 (3-connected).
I have worked this out on paper, there should be 11 different graphs.
Is there an efficient way to generate all possible graphs (with restrictions listed above) with n nodes where the degree of each node is specified ?
Thanks!
-Maxwell Day

  0 Comments

Sign in to comment.

Answers (1)

Christine Tobler
Christine Tobler on 24 Nov 2020
I've attached a script that computes the graphs in your example, here's the plot of all graphs it found:

  10 Comments

Show 7 older comments
Christine Tobler
Christine Tobler on 30 Nov 2020
Thanks for pointing this out, Maxwell. I made some last-minute modification that broke the code and didn't realize before. I've updated the file linked above, it should work now.
Maxwell Day
Maxwell Day on 30 Nov 2020
Thanks @Christine Tobler,
Now it appears the code is generating the Figure for each graph set properly!
I am attempting to run the degList = [2 2 2 2 3 3] with k = 8 and the following error shows up;
Error using nchoosek (line 29)
The second input has to be a non-negative integer.
Error in generateGraphsMultiNestedLoops (line 43)
lastSetsOfRows = nchoosek(firstSet(end)+1:size(ed, 1), e-k);
From your last comment, it sounds like increasing k should only decrease the memory required to a maximum value where k = e/2, where e = # of edges given by "degList", is this true? If so, should k always be set equal to e/2?
Christine Tobler
Christine Tobler on 30 Nov 2020
k must also be less than e, since we are splitting up the number of edges into k edges, and then e-k other edges. The error is because e-k becomes negative.

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by