0
$\begingroup$

I don't have Mathematica, yet, but I just wanted to know what the output of the following was:

GraphData["Cubic", 20]

I'm trying to understand how many unique not-necessarily-connected cubic graphs on $20$ vertices there are. Like, these are all connected cubic graphs on 20 vertices, but I know there are other arrangements (disjoint ones too). For example, you could have two cubic graphs on 4 vertices and two cubic graphs on 6 vertices, which gives 20 vertices all with degree 3, but there are four disjoint graphs that make them up. What am I looking for? I want to see all the unique ways 20 vertices can all have degree 3.


Update: GraphicsGrid[GraphData/@GraphData["Cubic",20],"AllImages"] produces the following: http://docdro.id/p9Rim76

$\endgroup$
  • 3
    $\begingroup$ GraphData queries a database. The answers it returns are not usually exhaustive. $\endgroup$ – Szabolcs Aug 8 '17 at 7:09
  • 2
    $\begingroup$ GraphData is complete when the number of graphs in question is not "too large". For example, it includes all simple graphs up to 7 nodes, all cubic graphs up to 10 nodes, etc. There are 516344 cubic graphs on 20 nodes; GraphData cannot possibly store data for them all. (There is however no reason it could not include all cubic graphs up to 14 nodes; I will add them for a future version.) $\endgroup$ – Eric Weisstein Aug 8 '17 at 15:14
  • $\begingroup$ @EricWeisstein, how can I see, like, the first 100 of those 516344 cubic graphs? $\endgroup$ – user51559 Aug 8 '17 at 16:47
  • $\begingroup$ Perhaps this article may help you? $\endgroup$ – Carl Woll Aug 8 '17 at 16:56
  • 1
    $\begingroup$ The article discusses generating connected cubic graphs, hence the discrepancy. $\endgroup$ – Carl Woll Aug 8 '17 at 17:30
0
$\begingroup$

Go here: link to online evaluator

Wait a moment for it to stabilize

Click on "Create a New Notebook" on the right side

Wait a moment for it to stabilize

Paste (or type) GraphData["Cubic", 20] into the large empty white space

Wait a moment for it to stabilize

Click Evaluation in the upper right and then click Evaluate Cells

Wait a moment for it to stabilize

It should display a list of the 29 kinds of graphs.

There are limitations and restrictions on the use of this. And please don't abuse this very nice free service.

Then there are lots of things about registering, signing in, saving, etc, etc. I do none of those. I just scrape the result and close the windows.

$\endgroup$
1
$\begingroup$

the output is :

{{CrossedPrism,10},CrossingNumberGraph6B,CrossingNumberGraph6C,{Cubic,{20,1}},{Cubic,{20,2}},{Cubic,{20,3}},{CubicTransitive,25},{CubicTransitive,28},DesarguesGraph,DodecahedralGraph,FiveTetrahedra,FlowerSnarkJ5,{GeneralizedPetersen,{10,4}},{Incidence,{{10,3},3}},{Incidence,{{10,3},5}},{Incidence,{{10,3},7}},{Incidence,{{10,3},8}},{Incidence,{{10,3},9}},{LargestCubicNonplanarDiameter,3},{MoebiusLadder,10},{Prism,10},{Snark,{20,1}},{Snark,{20,2}},{Snark,{20,3}},{Snark,{20,4}},{Snark,{20,5}},Two5MoebiusLadders,TwoPetersenGraphs,TwoY5}

$\endgroup$
  • $\begingroup$ Ok, now, how do I see all of them? $\endgroup$ – user51559 Aug 8 '17 at 16:05
  • $\begingroup$ Actually, GraphicsGrid[GraphData/@GraphData["Cubic",20],UpTo[7]] works for me. $\endgroup$ – user51559 Aug 8 '17 at 16:08
  • $\begingroup$ So, GraphicsGrid[GraphData/@GraphData["Cubic",20],"AllImages"] is incomplete? $\endgroup$ – user51559 Aug 8 '17 at 16:24
  • $\begingroup$ @uwnojpjm, what were you missing? $\endgroup$ – J. M. will be back soon Aug 8 '17 at 16:36
  • $\begingroup$ Someone said there were "516344" cubic nodes on 20 vertices. GraphData queries a database apparently, and it's not exhaustive. $\endgroup$ – user51559 Aug 8 '17 at 16:42
1
$\begingroup$

I don't know if this is an answer to the question or not, but I just wanted to put this here in case someone is interested in enumerating all the connected cubic graphs with 20 vertices, listed in this paper.

The house of graphs has a large collection of graphs in the "Graph6" format, which is just a string identifier with a Wolfram Language importer. This page (which grabs some info from here) lists the cubic graph enumerations for different vertex count and minimum girth.

Since the file we want is a half million lines long, and each line contains exactly one graph object, I'll import it as a stream. This allows me to monitor the progress, and get around Import's problems with large files.

file = URLDownload["https://hog.grinvin.org/data/cubics/cub20.g6"];

stream = OpenRead[file];
n = 0;
graphs20 = Table[
    n++;
    ImportString[
     ReadLine@stream,
     "Graph6"
     ]
    , {510489}
    ];~Monitor~n (* using Monitor to keep track of the progress *)

The above code took about 10 minutes on my machine. You can verify that you the importing went as planned,

Length@graphs20
(* 510489 *)

Head /@ graphs20 // Union
(* {Graph} *)

You can do whatever you like with the graphs now,

RandomSample[graphs10K, 10]

enter image description here

You could use VertexDegree to verify that they are all indeed cubic graphs,

cubicGraphQ = SameQ[VertexDegree[#] // Union, {3}] &

and finally write them to an MX file to save time importing them later

Export["cubicGraphs20.mx", graphs20]

Note that the exporte MX file is almost 500MB while the "Graph6" source file is only 17MB.

$\endgroup$

Your Answer

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