[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.
More information about the SeqFan
mailing list