# [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

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.
```