

A331905


Number of spanning trees in the multigraph cube of an ncycle.


2



1, 4, 12, 128, 605, 3072, 16807, 82944, 412164, 2035220, 9864899, 47579136, 227902597, 1084320412, 5134860060, 24207040512, 113664879137, 531895993344, 2481300851179, 11543181696640, 53565699079956, 248005494380204, 1145875775104967, 5284358088818688
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

The multigraph cube of an ncycle 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



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=(3sqrt(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 4cycle has four vertices, with two edges between each pair of distinct vertices  i.e., it is a doublededge 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> ((<<0100>, <0010>, <0001>, <1414>>^iquo(n, 2, 'd').
<[<0, 1, 4, 16>, <1, 2, 11, 49>][d+1]>)[1, 1])^2*n*(2irem(n, 2)):


CROSSREFS

Cf. A005822, A169630 (corresponding sequence for the multigraph square of an ncycle).


KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



