Group Abstract Group Abstract

Message Boards Message Boards

1
|
8.5K Views
|
10 Replies
|
10 Total Likes
View groups...
Share
Share this post:

Handle issues in connection with GraphData for Cubic graphs?

Posted 6 years ago
POSTED BY: Zs Sz
10 Replies
Posted 5 years ago

Alright, thank You very much! :)

POSTED BY: Zs Sz

IGraph/M now has its own DOI, and you can find citation information here: https://doi.org/10.5281/zenodo.1134932 There is a "cite as" box on the right hand side, a bit down on the page.

POSTED BY: Szabolcs Horvát
Posted 5 years ago

Dear Szabolcs,

Thank You for Your previous help. My last question is the following: How should we cite the IGraph/M package in our paper?

Thank You in advance.

POSTED BY: Zs Sz

I made a new release of IGraph/M which fixes the error checking in IGImport. Now it should not blow up if it gets unexpected input.

POSTED BY: Szabolcs Horvát

Great, I'm glad it worked :-)

POSTED BY: Szabolcs Horvát
Posted 6 years ago
POSTED BY: Zs Sz
POSTED BY: Szabolcs Horvát
POSTED BY: Szabolcs Horvát
Posted 6 years ago
POSTED BY: Zs Sz

GraphData is just a database a curated collection of graphs. As I remember, it is exhaustive up to 7 vertices, but above that, it only includes examples of special interest.

Do not use GraphData if you want all graphs with a certain property (at least not above $n=7$).

To generate all cubic graphs, I recommend the geng tool from the nauty suite. You will need to compile and install these tools on your own (unless your operating systems package manager has them; I usually get them with MacPorts).

geng outputs graphs in Graph6 format, which Mathematica's built-in Import can read, but IGImport in the IGraph/M package can read even faster. (IGraph/M also supports importing directed graphs in this format—Import currently does not.)

Get IGraph/M here: http://szhorvat.net/mathematica/IGraphM

Here's an example that counts how many cubic graphs are there on 12 vertices with different diameters:

IGImport["!geng -d3 -D3 12", "Nauty"] // Map[IGDiameter] // Counts // KeySort
(* <|3 -> 34, 4 -> 43, 5 -> 6, 6 -> 2, \[Infinity] -> 9|> *)

There are 34 with diameter 3, 43 with 4, etc. A diameter of Infinity means that the graph is disconnected.

-d3 -D3 in the geng call sets both the minimum and the maximum degree to 3. If you are not interested in disconnected graphs, we can filter those with -c.

Now we can go to bigger graphs: this only takes 1.5 seconds on my machine.

IGImport["!geng -d3 -D3 -c 16", "Nauty"] // Map[IGDiameter] // Counts // KeySort

(* <|3 -> 14, 4 -> 2167, 5 -> 1499, 6 -> 261, 7 -> 101, 8 -> 14, 9 -> 4|> *)
BarChart[%, ChartLabels -> Automatic]

enter image description here

POSTED BY: Szabolcs Horvát
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard