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

David Seal david.j.seal at gwynmop.com
Sun Feb 2 21:38:15 CET 2020

```Chris Thompson has pointed the following paper out to me:

Min Li, Zhibing Chen, Xiaoqing Ruan, Xuerong Yong,
The formulas for the number of spanning trees in circulant graphs,
Discrete Mathematics, Volume 338, Issue 11, 2015, Pages 1883-1906,
https://doi.org/10.1016/j.disc.2015.04.025

Its Lemma 1 provides a formula for A331905 (the number of spanning trees of the multigraph third power of a cycle): it is 1/nth of the product from j = 1 to n-1 of term(j) = (6 - 2cosO(j/n) - 2cosO(2j/n) - 2cosO(3j/n)), where cosO(x) = cos(2*pi*x) is the cosine function 'squashed' to have period 1. So the values of cosO() that are subtracted are the real parts of nth roots of unity - which suggests a connection with cyclotomic polynomials that I've yet to investigate (it may be in the above paper, whose results I have used without yet having really absorbed the proofs).

Anyway, it's easily observed that term(j) = term(n-j) and that if n is even, term(n/2) = 6 - 2cosO(0.5) - 2cosO(1) - 2cosO(1.5) = 6 - (-2) - 2 - (-2) = 8, so:

* if n is odd, A331905(n) = (1/n) * square(product from j = 1 to (n-1)/2 of term(j))
* if n is even, A331905(n) = (8/n) * square(product from j = 1 to n/2-1 of term(j))

Calculating a few of the products in that formulation, I found that they were all coming out as integers. At this point, I thought of Brendan's original observation about the sequence seeming to always be a multiple of A005822 - was it perhaps always a multiple of A005822 squared? This was easy to check:

n     A331905(n)  A005822(n)  A331905(n)/(A005822(n))^2
-------------------------------------------------------
1              1           1            1
2              4           1            4
3             12           2            3
4            128           4            8
5            605          11            5
6           3072          16           12
7          16807          49            7
8          82944          72           16
9         412164         214            9
10       2035220         319           20
11       9864899         947           11
12      47579136        1408           24
13     227902597        4187           13
14    1084320412        6223           28
15    5134860060       18502           15
16   24207040512       27504           32
17  113664879137       81769           17
18  531895993344      121552           36

The pattern seems pretty clear, so I conjecture that the connection between A005822 and A331905 is:

A331905(n) = n * (A005822(n))^2 if n is odd
2n * (A005822(n))^2 if n is even.

This is incidentally reminiscent of the result proved in the paper by Baron et al in the links from the sequences, that the corresponding sequence for the square of a cycle is n * (Fibonacci(n))^2, i.e. A169630.

David

> On 01 February 2020 at 01:21 David Seal <david.j.seal at gwynmop.com> wrote:
>
>
> Sorry I've been a bit slow to respond to Neil's request, but I have now submitted A331905. It's a rather 'bare bones' attempt, and I may well have missed important references, etc - but it's about all I can do at present.
>
> David
>
>
> > On 25 January 2020 at 16:50 Neil Sloane <njasloane at gmail.com> wrote:
> >
> >
> > I think David Seal is on the right track, when he says:
> >
> > > 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."
> >
> > and then the sequence would continue with the values that Brendan found.
> >
> > David, Could you please submit this sequence, and email me the A-number?
> > Then I will do some editing to  A005822. ( will change its definition to
> > the generating function, and say that the connection with trees is unclear.
> >
> >
> > Best regards
> > Neil
> >
> > Neil J. A. Sloane, President, OEIS Foundation.
> > 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> > Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
> > Email: njasloane at gmail.com
> >
> >
> >
> > On Sat, Jan 25, 2020 at 9:55 AM David Seal <david.j.seal at gwynmop.com> wrote:
> >
> > > > 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
> > >
> > > --
> > > Seqfan Mailing list - http://list.seqfan.eu/
> > >
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/

```