The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A331905 Number of spanning trees in the multigraph cube of an n-cycle. 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 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 * A053551 A009663 A197899 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified November 29 09:50 EST 2023. Contains 367429 sequences. (Running on oeis4.)