# [seqfan] Spanning trees in the cube of a cycle (A005288)

Brendan McKay Brendan.McKay at anu.edu.au
Sat Jan 25 02:30:55 CET 2020

```It has been noticed on Mathoverflow that something is amiss with A005288
"Number of spanning trees in third power of cycle".

A5288(n) = 1, 1, 2, 4, 11, 16, 49, 72, 214, 319, 947, 1408, 4187,
6223, 18502, 27504
offset: 1,3

The simplest proof that there's a problem is that there is no graph on
3 vertices with 2 spanning trees.

I take "third power of cycle" to mean a graph whose edges join vertices arranged
in a cycle if they are at most 3 apart.  Up to 7 vertices it is a complete graph,
so the number of spanning trees is n^(n-2).  Starting at 7 vertices it is a
regular graph of degree 6.

By direct computation using the matrix tree theorem, I get actual values
T(n) = 1, 1, 3, 16, 125, 1296, 16807, 82944, 412164, 2035220, 9864899,
47579136, 227902597, 1084320412, 5134860060, 24207040512,
113664879137, 531895993344

I'm sure there is some relationship between A5288(n) and T(n) since
for n >= 7 and as far as I computed T(n) is a multiple of A5288(n).  Here
is the ratio T(n)/A5288(n) starting at n=7:  1152, 1926, 6380, 10417, 33792,
54431, 174244, 277530, 880128, 1390073, 4375872

I conjecture  that T(n) = f(n)*A5288(n) for some f(n) that has been lost,
and that this relation is only intended to hold for n>=7, or maybe n>=8.

The cited works of Plouffe probably contain the explanation, but my
French is not up to it.

Brendan.
```