Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I am attempting to use the Combinatorica NumberOfSpanningTrees command for all n-cycle graphs from 3 to 30. I am trying to get a table form showing whether it is true or false that n-cycle graphs have n spanning trees. However Mathematica does not seem to recognize the command. Am I am pre-loading the Combinatorica packages correctly?

<< Combinatorica`
Table[{i, NumberOfSpanningTrees[CycleGraph[i]] == i}, {i, 3, 30}] // TableForm

The output I get is:

enter image description here

I have also tried loading Combinatorica using the Needs["Combinatorica"].

Any ideas?

share|improve this question
add comment

2 Answers

up vote 12 down vote accepted

The Combinatorica package is now considered obsolete and not compatible with Mathematica's built-in Graph theory functionality. The function CycleGraph, which you are using, is a built-in function and is not understood by the Combinatorica package. You have to replace CycleGraph[i] simply by Cycle[i], which is the corresponding object in Combinatorica. You can confirm this that by looking at (for example) CycleGraph[5] and ShowGraph[Cycle[5]]:

GraphicsRow[{CycleGraph[5] , ShowGraph[Cycle[5]]}]

Mathematica graphics

Actually, the Combinatorica package still has a lot of functionality that has nothing equivalent in the Kernel (and it is not clear if this will ever change completely). On the other hand it is essentially undocumented (unless you buy the book by Skiena and Pemmaraju) and the quality of Mathematica programming is not great (there are also bugs that never seem to get fixed).

share|improve this answer
    
Your answer worked perfectly. The difference of the commands between Combinatorica and Mathematica still confuses me. –  Nic Young Mar 27 '12 at 3:34
    
@NicYoung Maybe it's also useful to know that you can convert a new style graph to a Combinatorica graph using the ToCombinatoricaGraph function of the GraphUtilities` package. –  Szabolcs Mar 27 '12 at 7:06
add comment

Without using the Combinatorica package, you can use

 Table[{i, GraphData[{"Cycle", i}, "SpanningTreeCount"] == i}, 
{i, 3, 20}] // TableForm

to get

 {{3, True}, {4, True}, {5, True}, {6, True}, {7, True}, {8, True}, 
 {9, True}, {10, True}, {11, True}, {12, True}, {13, True}, {14, True}, 
 {15, True}, {16, True}, {17, True}, {18, True}, {19, True}, {20, True}}

This does not work for i>20 since GraphData contains named cycle graphs {"Cycle", i} for i<=20.

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.