[seqfan] Help needed

Richard Guy rkg at cpsc.ucalgary.ca
Fri Mar 12 23:54:01 CET 2010

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


  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.

More information about the SeqFan mailing list