[seqfan] Re: Help needed

[Richard Guy]

The outstanding questions are these:

(a) shouldn't there be two sequences:

     (1) n * Fib^2,  (2) # of spanning trees
of some graph or other  ??   [note that
the first few Kleitman - Golden values
are NOT  n * Fib^2  -- unless perhaps
you cook it by allowing repeated edges
in some of the smaller graphs.

(b) what is the graph?  what is the square
of a cycle?

(c) what is the cube of a cycle? [as in the
heading of A005822]  And is the sequence
A005822 relevant to the Baron et al paper
quoted there?  Note that the sequence of
that paper is purportedly the same as that
in Kleitman-Golden (and not the same as
n * F(n)^2 until you get to  n = 5).  R.

On Fri, 12 Mar 2010, Richard Guy wrote:

> I don't find the sequence ..., 125, 384, 1183, ...
> in OEIS, though it is evidently (part of) that
> found in the papers
>
> MR0364002 (51 #257)
> Kleitman, D. J.; Golden, B.
> Counting trees in a certain class of graphs.
> Amer. Math. Monthly 82 (1975), 40--44.
>
> Let $G_n$ denote the graph with nodes, $1,2,\cdots,n$, in which nodes $i$ and 
> $j$ are joined if and only if the difference between $i$ and $j$, modulo $n$, 
> equals one or two. The authors show that $G_n$ has $nf_n{}^2$ spanning trees, 
> where $f_n$ denotes the $n$th Fibonacci number.
> Reviewed by J. W. Moon
>
> and
>
> MR0806296 (87c:05045)
> Baron, G.(A-TUWN); Prodinger, H.(A-TUWN); Tichy, R. F.(A-TUWN); Boesch, F. 
> T.(1-STIT); Wang, J. F.(RC-TAIN)
> The number of spanning trees in the square of a cycle.
> Fibonacci Quart. 23 (1985), no. 3, 258--264.
>
> The number mentioned in the title is $n$ times the square of the $n$th 
> Fibonacci number, where $n$ is the length of the cycle. This result has been 
> found by \n D. J. Kleitman\en and \n B. Golden\en [Amer. Math. Monthly 82 
> (1975), 40--44; MR0364002 (51 #257)] by purely combinatorial methods. In the 
> present paper the formula is proved by Kirchhoff's matrix tree theorem.
> Reviewed by J. Sedláček
>
> There are (for me) two (at least) difficulties:
>
> (a) the earlier members of the sequence,
>
> 0, 1, 2, 12, 36,
>
> may not be appropriate to the definitions
> in the papers.
>
> (b)  I can't reconcile the definitions
> of the graph.  Shouldn't  C_n^2, the
> square of the n-cycle, have  n^2  vertices
> and  2n^2  edges, being 4-valent?  The pix
> in Kleitman & Golden are indeed 4-valent,
> but have only  n  vertices and  2n  edges.
>
> And what is ``the third power of a cycle''
> [A005822] -- which refers to the Baron et
> al paper ?       R.
>