11
$\begingroup$

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?

$\endgroup$
13
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Your answer worked perfectly. The difference of the commands between Combinatorica and Mathematica still confuses me. $\endgroup$ – Nic Young Mar 27 '12 at 3:34
  • 1
    $\begingroup$ @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. $\endgroup$ – Szabolcs Mar 27 '12 at 7:06
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

NumberOfSpanningTrees is a Combinatorica package function. CycleGraph is part of the built-in Graph framework. Combinatorica and the built-in Graph are distinct and incompatible.

The IGraph/M package now includes a function to count spanning trees, IGSpanningTreeCount. IGraph/M is designed to be compatible with and complement the built-in Graph functionality.

IGSpanningTreeCount[CycleGraph[3]]
(* 3 *)

This function also works with multigraphs and directed graphs.

Count the spanning trees of a directed 3-cycle:

IGSpanningTreeCount[CycleGraph[3, DirectedEdges -> True]]
(* 3 *)

Count the spanning trees that are rooted in vertex 1.

IGSpanningTreeCount[CycleGraph[3, DirectedEdges -> True], 1]
(* 1 *)

A non-strongly-connected directed graph has no spanning trees.

IGSpanningTreeCount[Graph[{1 -> 2, 3 -> 2}]]
(* 0 *)

With these extensions, IGSpanningTreeCount is more flexible than what Combinatorica includes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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