# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/ Search: id:a331905 Showing 1-1 of 1 %I A331905 #45 May 02 2022 20:46:40 %S A331905 1,4,12,128,605,3072,16807,82944,412164,2035220,9864899,47579136, %T A331905 227902597,1084320412,5134860060,24207040512,113664879137, %U A331905 531895993344,2481300851179,11543181696640,53565699079956,248005494380204,1145875775104967,5284358088818688 %N A331905 Number of spanning trees in the multigraph cube of an n-cycle. %C A331905 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. %C A331905 Baron et al. (1985) describes the corresponding sequence A169630 for the multigraph square of a cycle. %C A331905 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) %C A331905 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. %H A331905 Alois P. Heinz, Table of n, a(n) for n = 1..1546 %H A331905 G. Baron et al., The number of spanning trees in the square of a cycle, Fib. Quart., 23 (1985), 258-264. %H A331905 Yoshiaki Doi et al., A note on spanning trees %H A331905 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. %F A331905 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 %e A331905 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. %p A331905 a:= n-> ((<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <-1|4|1|4>>^iquo(n, 2, 'd'). %p A331905 <[<0, 1, 4, 16>, <1, 2, 11, 49>][d+1]>)[1, 1])^2*n*(2-irem(n, 2)): %p A331905 seq(a(n), n=1..30); # _Alois P. Heinz_, Feb 06 2020 %Y A331905 Cf. A005822, A169630 (corresponding sequence for the multigraph square of an n-cycle). %K A331905 nonn %O A331905 1,2 %A A331905 _David J. Seal_, Jan 31 2020 %E A331905 More terms from _Alois P. Heinz_, Feb 06 2020 # Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE