A331905 Number of spanning trees in the multigraph cube of an n-cycle.

1, 4, 12, 128, 605, 3072, 16807, 82944, 412164, 2035220, 9864899, 47579136, 227902597, 1084320412, 5134860060, 24207040512, 113664879137, 531895993344, 2481300851179, 11543181696640, 53565699079956, 248005494380204, 1145875775104967, 5284358088818688

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

Cf. A005822, A169630 (corresponding sequence for the multigraph square of an n-cycle).

Sequence in context: A285451 A249788 A032323 * A367885 A053551 A009663

Adjacent sequences: A331902 A331903 A331904 * A331906 A331907 A331908

Keyword

nonn

Author

David J. Seal, Jan 31 2020

Extensions

More terms from Alois P. Heinz, Feb 06 2020

Status

approved