Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Also, it would be nice to be able to exclude graphs which are not connected. –  utdiscant Mar 17 '11 at 22:00
add comment

2 Answers 2

up vote 2 down vote accepted

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"]

share|improve this answer
    
markdown doesn't recognize link to wikipedia's Kirkhoff's theorem because it has an apostrophe in it, any idea how to make the link work? –  Yaroslav Bulatov Mar 18 '11 at 11:08
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.