1
$\begingroup$

Suppose I want to generate all graphs satisfying some properties (specifically 2-connected graphs on 30 vertices with degree sequence $(4, 4, 3, 3,3, \dotsc, 3)$). Unfortunately, there are an enormous number of such graphs. Probably the fastest way to find all of them would to use nauty, but it is too slow.

Is there a way to just generate many such graphs (i.e., not needing a complete list)?

There isn't an obvious way to get nauty to output just the first 10 million graphs, for instance. Maybe this isn't even possible, I don't know how nauty works.

$\endgroup$
  • $\begingroup$ 1. I think you mean naive and not nauty. 2. Almost all such graphs (30 vertices and your degree sequence) are isomorphic. You can just rename vertices in the first to get them all. If you mean for any given sequence, it's much harder. $\endgroup$ – rus9384 Aug 28 '17 at 2:33
  • 1
    $\begingroup$ @rus9384 unless he meant nauty $\endgroup$ – Evil Aug 28 '17 at 2:38
  • $\begingroup$ @Evil, oh, now I understand. $\endgroup$ – rus9384 Aug 28 '17 at 2:42
3
$\begingroup$

There are methods for randomly sampling graphs with a given degree sequence. You could try sampling and post-selecting for 2-connectedness, since that test is essentially a DFS. See for example

Efficient and Exact Sampling of Simple Graphs with Given Arbitrary Degree Sequence

$\endgroup$
1
$\begingroup$

Maybe SageMath can help you with this. Not sure how performance will compare to nauty.

For example, to generate 10 biconnected graphs on 8 vertices with degree sequence [4,4,3,3,3,3,3,3] you can use

sage: deg_seq=[4,4]+[3 for i in range(6)]
sage: graph_gen=graphs(8,degree_sequence=deg_seq)
sage: for i,g in enumerate(graph_gen):
....:     if i==10:
....:         break
....:     if g.is_biconnected():
....:         # do something with g

See documentation for details.

Also, SageMath has a nauty interface, maybe you can use it there to generate the graphs. Reading on how to use geng can be useful, however not so sure about how to restrict the degree sequence directly. Perhaps you can get help through their mailing list?


Update: property is ignored when degree_sequence is provided to graphs.

$\endgroup$
  • $\begingroup$ The problem is not generating graphs, it is easy to do that using nauty (since every graph on 46 edges with minimum degree 3 and max degree 4 has this degree sequence). The trouble is that there are too many of them (probably around $10^{12}$). For that sage code too it seems like it generates all the graphs satisfying those properties. $\endgroup$ – vukov Aug 28 '17 at 4:38
  • $\begingroup$ They way the code above works is via Python generators. That is, graphs are generated one graph at a time. If you iterate through the for loop only 10 times, then only 10 graphs are actually generated (one at a time). Through nauty you have the option of using the res mod argument to restrict to a subset of the generated graphs. $\endgroup$ – fidbc Aug 28 '17 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.