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

[David Seal]

> On 25 January 2020 at 01:30 Brendan McKay <Brendan.McKay at anu.edu.au> wrote:
> ...
> 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.

I observe that if one takes "third power of cycle" to mean the multigraph whose edges join vertices arranged in a cycle if they are at most 3 apart, with multiple edges sometimes appearing between vertices if the cycle has 6 or fewer vertices (following what the penultimate page of http://www.fq.math.ca/Scanned/23-3/baron.pdf does for 4 or fewer vertices in the square of a cycle), then the first six values of T(n) rise to 1, 4, 12, 128, 605, 3072. That makes it always be a multiple f(n)*A005822(n) of A005822(n), with the first six values of f(n) being 1, 4, 6, 32, 55, 192.

This tends to confirm that A005822 really is something to do with third powers of cycles, but I'm afraid I haven't managed to work out what!

David