[seqfan] Re: Spanning trees in the cube of a cycle (A005288)
njasloane at gmail.com
Sat Jan 25 08:24:48 CET 2020
It is possible that the article
D. J. Kleitman and B. Golden. "Counting Trees in a Certain Class of
Graphs." Amer. Math. Montlhy (1975), pp. 40-44. Vol 82, Number 1,
may be relevant, but my Rutgers library login has suddenly stopped working
and it 2am here .
Could someone get me a copy?
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 2:03 AM Neil Sloane <njasloane at gmail.com> wrote:
> 1. I will ask Simon Plouffe if he can remember anything about this
> 2. I checked my old files, but did not find anything on an initial search
> 3. If all else fails, I suggest we change the definition of A005822 to
> the generating function
> (1-x^2)*(x^4+x^3-x^2+x+1) / (x^8-4*x^6-x^4-4*x^2+1)
> and then Brendan you could submit your version that matches the words of
> the present definition as a new sequence.
> But let's wait to hear from Simon.
> Simon, Can you throw any light on A005822 (aka M1243)?
> Best regards
> 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 Fri, Jan 24, 2020 at 11:58 PM Brendan McKay <Brendan.McKay at anu.edu.au>
>> Yes, sorry, A005822. Edited below. Brendan.
>> On 25/1/20 1:26 pm, Sean A. Irvine wrote:
>> > You mean A005822 ...
>> > On Sat, 25 Jan 2020 at 14:31, Brendan McKay <Brendan.McKay at anu.edu.au>
>> > wrote:
>> >> It has been noticed on Mathoverflow that something is amiss with
>> >> "Number of spanning trees in third power of cycle".
>> >> A5822(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
>> >> 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
>> >> 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).
>> >> is the ratio T(n)/A5822(n) starting at n=7: 1152, 1926, 6380, 10417,
>> >> 33792,
>> >> 54431, 174244, 277530, 880128, 1390073, 4375872
>> >> I conjecture that T(n) = f(n)*A5822(n) for some f(n) that has been
>> >> and that this relation is only intended to hold for n>=7, or maybe
>> >> The cited works of Plouffe probably contain the explanation, but my
>> >> French is not up to it.
>> >> Brendan.
>> >> --
>> >> Seqfan Mailing list - http://list.seqfan.eu/
>> > --
>> > Seqfan Mailing list - http://list.seqfan.eu/
>> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan