0
$\begingroup$

I'm trying to make the list of all 2-connected subcubic graphs with at most N vertices.

I tried this code:

GraphData[All, "Preload"]
Select[GraphData[7], (GraphData[#, "EdgeChromaticNumber"] == 3 && GraphData[#, "VertexConnectivity"] >= 3) &]

I found this code here, but it gave me the next error:

error

Can somebody help me?

Rk. N can be fixed at the beginning, we would like to take N as big as possible as long as the computation is still feasible.

$\endgroup$
12
  • 4
    $\begingroup$ You mean an exhaustive list, for 100 points? That is unreasonable. There will be more such graphs than what could fit in the memory of all computers in the world, combined. $\endgroup$ – Szabolcs Mar 21 '20 at 11:29
  • 2
    $\begingroup$ Please formulate the problem precisely, so people will not spend time creating solutions that you will not find useful. You talk about vertex connectivity, but the code you show deal with edge chromatic numbers. It's unclear how many such graphs you want (it's easy to make as many as you want as basically all sufficiently dense random graphs will be 3-connected). $\endgroup$ – Szabolcs Mar 21 '20 at 11:31
  • $\begingroup$ Thanks for the edit, but it still has not answered the questions I raised ... $\endgroup$ – Szabolcs Mar 21 '20 at 12:32
  • $\begingroup$ I wrote a code I need to test on as many 3-connected graphs with degree at most 3 in each vertice and a maximum amount of points. My mentor suggested I try it for 100 vertices, but if you think this is impossible, I could also try less. I'm not very skilled in Mathematica so I tried the code I found there, but as you pointed out it is wrong. What questions do you still have that I didn't answer in the edit? $\endgroup$ – Debbie Mar 21 '20 at 16:37
  • 2
    $\begingroup$ @MaurizioMoreschi geng from the nauty suite can do this, if you want 2-connected. But Debbie said 3-connected. It makes a big difference. $\endgroup$ – Szabolcs Mar 21 '20 at 18:58
2
$\begingroup$

Since there was a lot of confusion about the OP's requirements, I am going to repeat the problem:

Exhaustively generate all non-isomorphic biconnected graphs with maximum degree 3 on $n$ vertices, for as large an $n$ as feasible.

I highly recommend using the geng tool from the nauty suite. You will need to compile this collection of programs yourself, but it is very easy to do it on Mac or Linux.

geng outputs the result in the graph6 format. Mathematica can import this format using the built-in Import, but I highly recommend that you use IGImport from my IGraph/M package instead. It will give a ~3x speedup. The bottleneck will unfortunately still be the importing, not running geng itself.

We set these geng options (see geng -help): -C for biconnected, -d2 for minimum degree 2 (since we want biconnected) and -D3 for maximum degree 3.

There are 165,993 such graphs on 15 vertices and it took ~15 seconds to generate and import them on my machine.

IGImport["!/opt/local/bin/geng 15 -d2 -D3 -C", "Graph6"] // Length // AbsoluteTiming
(* {14.9616, 165993} *)

For 14 vertices,

IGImport["!/opt/local/bin/geng 14 -d2 -D3 -C", "Graph6"] // Length // AbsoluteTiming
(* {3.82645, 43418} *)

These timings should give a hint about how large an $n$ is feasible.

In the command above, I wrote the full path to the geng executable on my computer. This will be different on yours: adjust it. Note the ! before the executable: this tells Import to execute the command and import whatever it outputs.

$\endgroup$

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.