How to generate all the matrices of graphs for given numbers of vertices and edges?

Hi, everyone. Assuming all the nodes are equivalent. I wanna generate all the possible matrices to describe undirected graphs whose numbers of vertices and edges are given.

e.g. n=4 is the number of vertices and m=3 is the number of edges.

Then the possible graphs are type1:1-2-3-4, type2:1-2-4.

2 |

| 3

no 2-1-3-4 or 1-3-4,...., because all the vertices are indistinguishable.

then the code can give me the matrices as [0 1 1 1; 1 0 0 0; 1 0 0 0; 1 0 0 0] and [0 1 0 1; 1 0 1 1; 0 1 0 0; 0 1 0 0] which respectively describes the links in type1 and type 2(if it can show graphs is better).

So is there any command or function can do this? Any help is appreciated. Thanks!

[Guillaume]

Why is 2-1-3-4 not valid? It is absolutely not the same graph as 1-2-3-4.

In any case, no there is no function to generate all possible graphs with a fixed number of edges and nodes. You would have to write your own. I suspect that it is not a trivial job.

[Yichao Li]

Thanks for your answer! 2-1-3-4 is not valid because here all the vertices are indistinguishable so topologically, 1-2-3-4 is equivalent to 2-1-3-4.

Actually this question has been solved by Mathematica, but still thanks for your effort.

[Siddhikant Mishra]

could you give me the link to the mathmatica solution?

Answer 1

[Christine Tobler]

I've attached a script that computes this for n=4 and e=3. This script will not scale well to larger numbers of nodes and edges, but should work pretty well for small cases.

There are some comments in the attachment, hope these are clear enough.

[Yichao Li]

Actually this question has been solved by Mathematica, but still thanks for your effort!

[Maxwell Day]

Hi @Christine Tobler, the generateGraphs.m code has been extremely helpful to me. Thank you.

Instead of specifying n and e, how could the code be revised to specify n (# of nodes) and a value d (degree of each of those nodes) for each value of n? E.g. revise the code to generate all possible graphs with 2 vertices of degree 2 and 2 vertices of degree 3?

Is there anyway to revise the code to allow for loops and multi-edges?, when I refer to multiedges I wish to generate graphs where up to two edges between any two vertices are allowed.

Thanks again!

-Maxwell Day