[seqfan] Re: Help needed

[Richard Mathar]

The Kleitman-Golden graphs G_n are also considered by

Vohra, Wahsington, "Counting spanning trees in the graphs
of Kleitman and Golden and a Generalization",
J. Frankl Inst. 318 (1984) p 349
http://www.cs.ust.hk/mjg_lib/Library/Vorha_Washington_84.pdf
The article is clearer in which nodes are actually connected than the striped
layers in other publications, for example

Koganov, "Coding and counting spanning trees in Kleitman-Golden Graphs",
Cybern. Systems An. 27 (1991) 311
http://dx.doi.org/10.1007/BF01068310

The wording "square cycle" seems to refer to the product
of two graphs and is also used in the related article
by
Hou, Woo, Chen, "On the sandpile group of the square Cycle C_n^2",
Linear Algebra Applic 418 (2006) 457,
http://dx.doi.org/10.1016/j.laa.2006.02.02

So I guess that "cycle cube" refers to cycles in the C_n X C_n X C_n
graphs.

A generalization of these circulant graphs is in
Zhang, Yong, Golin, "The number of spanning trees in
circulatn graphs", Discr. Math 223 (2000) 337
http://hdl.handle.net/1783.1/466
See Theorem 9.

and

Atajan, Yong, Inaba, "An efficient approach for counting
the number of spanning trees in circulant and related graphs"
Discr. Math. 310 (2010)1210 
http://dx.doi.org/10.1016/j.disc.2009.11.033

and

Golin, Leung, "Unhooking circulant graphs: A combinatorial
method for counting spanning trees and other parameters)
http://www.cs.ust.hk/~golin/pubs/golin_WG04.pdf

and

Chen, Lin, Zhang, "The number of spanning trees in
odd valent circulant graphs", Discr Math 282 (2004) 69-79
http://dx.doi.org/10.1016/j.disc.2003.12.006

Richard J. Mathar