OFFSET
1,2
COMMENTS
The multigraph cube of an n-cycle has n nodes V1, V2, ... Vn, with one edge Vi to Vj for each pair (i,j) such that j = i+1, i+2 or i+3 modulo n. It is a multigraph when n <= 6 because this produces instances of multiple edges between the same two vertices, and it also produces loops if n <= 3.
Baron et al. (1985) describes the corresponding sequence A169630 for the multigraph square of a cycle.
I conjecture that a(n) = gcd(n,2) * n * (A005822(n))^2. [This is correct - see the Formula section. - N. J. A. Sloane, Feb 06 2020)
Terms a(7) to a(18) calculated by Brendan McKay, and terms a(1) to a(6) by David J. Seal, in both cases using Kirchhoff's matrix tree theorem.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..1546
G. Baron et al., The number of spanning trees in the square of a cycle, Fib. Quart., 23 (1985), 258-264.
Yoshiaki Doi et al., A note on spanning trees
Min Li, Zhibing Chen, Xiaoqing Ruan, and Xuerong Yong, The formulas for the number of spanning trees in circulant graphs, Disc. Math. 338 (11) (2015) 1883-1906, Lemma 1.
FORMULA
The following formulas were provided by Tsuyoshi Miezaki on Feb 05 2020 (see Doi et al. link). Let z1=(-3+sqrt(-7))/4, z2=(-3-sqrt(-7))/4; T(n,z) = cos(n*arccos(z)). Then a(n) = (2*n/7)*(T(n,z1)-1)*(T(n,z2)-1). Furthermore a(n) = 2*n*A005822(n)^2 if n is even, or n*A005822(n)^2 if n is odd. - N. J. A. Sloane, Feb 06 2020
EXAMPLE
The multigraph cube of a 4-cycle has four vertices, with two edges between each pair of distinct vertices - i.e., it is a doubled-edge cover of the complete graph on 4 vertices. The complete graph on 4 vertices has 4^2 = 16 spanning trees, and each of those spanning trees corresponds to 8 spanning trees of the multigraph tree because there are independent choices of 2 multigraph edges to be made for each of the three edges in the graph's spanning tree. So a(4) = 16 * 8 = 128.
MAPLE
a:= n-> ((<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <-1|4|1|4>>^iquo(n, 2, 'd').
<[<0, 1, 4, 16>, <1, 2, 11, 49>][d+1]>)[1, 1])^2*n*(2-irem(n, 2)):
seq(a(n), n=1..30); # Alois P. Heinz, Feb 06 2020
CROSSREFS
KEYWORD
nonn
AUTHOR
David J. Seal, Jan 31 2020
EXTENSIONS
More terms from Alois P. Heinz, Feb 06 2020
STATUS
approved