[seqfan] Re: Help needed
Richard Guy
rkg at cpsc.ucalgary.ca
Sun Mar 14 03:25:28 CET 2010
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.
>
More information about the SeqFan
mailing list