Union on Graph Data in Mathematica

Question

I have begun working with Mathematica for some Graph Theory, and I want to compute the number of spanning trees of all cubic graphs up to 12 vertices. I have found that

GraphData["Cubic", 12]

will give me the cubic graphs with 12 vertices. But how do I compute the number of spanning trees in each of these graphs. A good tutorial for Graph Theory with Mathematica seems impossible to find (I have found many, but none are actually readable). I can find this:

GraphData[8]; Union[GraphData[#, "VertexCount"] & /@ %%]

to compute the number of vertices in all graphs on 8 vertices, but the #-tag is not defined, and &/@%% seems pretty magical.

Answer 1

To help figure out a Mathematica expression, following is useful

GraphData[8]; Union[GraphData[#, "VertexCount"] & /@ %%] // Hold // TreeForm

Also, try FullForm instead of TreeForm

Since GraphData has property SpanningTreeCount, you could do

graphs = GraphData[{"Cubic", "Connected"}, 12];
counts = GraphData[#, "SpanningTreeCount"] & /@ graphs;
Column@Thread@{counts, graphs}

Alternatively, you could get number of spanning trees from Laplacian matrix of the graph using Kirchoff's matrix tree theorem.

kirk[L_] := Det@Drop[L, {1}, {1}];
counts = kirk[GraphData[#, "LaplacianMatrix"]] & /@ graphs;

The Drop command drops 1st row and 1st column of the matrix, but you could drop any other row/column.

To display 12 vertex cubic graphs nicely, with graph name in tooltip and sorted by number of spanning trees, you could do something like this

count[name_] := GraphData[name, "SpanningTreeCount"];
showCount[name_] := Show[GraphData@name, PlotLabel -> count@name];
showLabeledCount[name_] := Tooltip[showCount@name, name];
graphs = GraphData["Cubic", 12];
pics = showLabeledCount /@ Sort[graphs, count[#1] < count[#2] &];
pics = ArrayPad[pics, {0, 2}, Graphics[]];
GraphicsGrid@Partition[pics, 10]

To get all cubic, connected graphs with up to 12 vertices (disconnected graphs are not interesting since they have 0 spanning trees), do GraphData[{"Cubic", "Connected"}, ;; 12]

If you are doing graph theory with Mathematica, you could find my graph utilities packages helpful, documented here, here, and here. For instance, with showGraphs package, you could display all Cubic graphs over 12 vertices that are not connected with showGraphs[12,"Cubic",!"Connected"]

Answer 2

First, let's pick apart the command you mention.

Union[GraphData[#, "VertexCount"] & /@ %%]

GraphData[#, "VertexCount"]& is the same as Function[x, GraphData[x, "VertexCount"]]. That is, the # is an input parameter and the & terminates the expression of the # parameter to be considered a function. %% is the result-before-last (% is the most recent result, %% is the one before that, %%% is the one before that one, etc.). /@ applies a function to each item of a list. So, GraphData[#, "VertexCount"] & /@ %% returns the list that results from applying the function GraphData[#, "VertexCount"]& to each element of the list in %%. Because of the %%, the line

GraphData[8]; Union[GraphData[#, "VertexCount"] & /@ %%]

is probably out of context (since %% should refer to the result of the statement before GraphData[8]), and beyond saying that Union[] gives the union of sets, I can't tell what it's doing here because I don't know to what %% refers.

---

Now, back to what you're trying to do. GraphData[some_graph, "SpanningTreeCount"] will give the number of spanning trees for *some_graph* (I think, based on the documentation for GraphData), so GraphData[#, "SpanningTreeCount"] & /@ GraphData["Cubic", 12] will give a list containing the number of spanning trees for each of the cubic graphs with 12 vertices, and

Total[GraphData[#, "SpanningTreeCount"] & /@ GraphData["Cubic", 12]]

will give the total of the numbers in that list.

Also, since GraphData[#, "Connected"]& is a function that returns True for connected graphs and False otherwise,

Select[GraphData["Cubic", 12], GraphData[#, "Connected"] &]

will give you a list of only the connected cubic graphs with 12 vertices.