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

[Neil Sloane]

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.
Phone: 732 828 6098; home page: http://NeilSloane.com
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/
>