Does the Wolfram database of graphs include all connected graphs when the number of vertices is <= 8?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Look in en.wikipedia.org/wiki/Connectivity_(graph_theory). $\endgroup$– user64494Commented Feb 18, 2017 at 10:19
-
2$\begingroup$ @user64494 That table is for labelled graph, but GraphData does not have isomorphic duplicates. $\endgroup$– SzabolcsCommented Feb 18, 2017 at 10:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
We can get the number of connected graphs on $k$ nodes that are contained in GraphData as follows:
Table[Length@GraphData["Connected", k], {k, 1, 8}]
(* {1, 1, 2, 6, 21, 112, 853, 215} *)
Let us compare this to the total number of connected unlabelled graphs on $k$ nodes, which is recorded in OEIS A001349:
1, 1, 2, 6, 21, 112, 853, 11117
We see that up to 7 nodes, GraphData has all of them. But it only has 215 connected graphs on 8 nodes, while the total number is 11,117.
answered Feb 18, 2017 at 10:15