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

[David Seal]

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.
> 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/
> >
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/