A138179 Wiener index of the prism graph Y_n on 2n nodes.

1, 8, 21, 48, 85, 144, 217, 320, 441, 600, 781, 1008, 1261, 1568, 1905, 2304, 2737, 3240, 3781, 4400, 5061, 5808, 6601, 7488, 8425, 9464, 10557, 11760, 13021, 14400, 15841, 17408, 19041, 20808, 22645, 24624, 26677, 28880, 31161, 33600, 36121, 38808

Offset: 1

Author

Eric W. Weisstein, Mar 04 2008

Keywords

• nonn
• easy

Comments

Sequence expended to a(1)-a(2) using the formula/recurrence. - Eric W. Weisstein, Sep 08 2017

Apparently a(n) = n * A074148(n), so a(n)= +2*a(n-1) +a(n-2) -4*a(n-3) +a(n-4) +2*a(n-5) -a(n-6). - R. J. Mathar, May 31 2010

From Emeric Deutsch, Sep 16 2010: (Start)

The Wiener index of a connected graph is the sum of all distances in the graph.

Y_n is also called circular ladder (= P_2 X C_n, where P_2 is the path graph on 2 nodes and C_n is the cycle graph on n nodes).

a(n) = Sum(k*A180572(n,k), k>=1).

a(n) is the derivative of the Wiener polynomial of Y_n (given in A180572) evaluated at t=1. (see the Sagan et al. reference).

(End)

Examples

			a(3) = 21 because the triangular prism has 9 distances equal to 1 (the edges) and 6 distances equal to 2 (from the vertices of the lower base to the "opposite" vertices of the upper base). - _Emeric Deutsch_, Sep 16 2010
		

References

• J. Gross and J. Yellen, Graph Theory and its Applications, CRC, Boca Raton, 1999 (p. 14). - Emeric Deutsch, Sep 16 2010

Links

• Colin Barker, Table of n, a(n) for n = 1..1000 (corrected by Michel Marcus, Jan 19 2019)
• B. E. Sagan, Y-N. Yeh and P. Zhang, The Wiener Polynomial of a Graph, Internat. J. of Quantum Chem., 60, 1996, 959-969. - _Emeric Deutsch_, Sep 16 2010
• Y.-N. Yeh and I. Gutman, On the sum of all distances in composite graphs, Discrete Math., 135 (1994), 359-365 (set m=2 in the formula for W(Cyl_{m,n}) on p. 363). - _Emeric Deutsch_, Sep 16 2010
• Eric Weisstein's World of Mathematics, Prism Graph
• Eric Weisstein's World of Mathematics, Wiener Index
• Index entries for linear recurrences with constant coefficients, signature (2,1,-4,1,2,-1).

Crossrefs

Cf. A180572

Programs

Mathematica

LinearRecurrence[{2, 1, -4, 1, 2, -1}, {1, 8, 21, 48, 85, 144}, 40] (* Harvey P. Dale, Jul 29 2013 *)
Table[1/4 n (-1 + (-1)^n + 2 n (2 + n)), {n, 20}] (* Eric W. Weisstein, May 11 2017 *)
CoefficientList[Series[(1 + 6 x + 4 x^2 + 2 x^3 - x^4)/((-1 + x)^4 (1 + x)^2), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 08 2017 *)

PARI

Vec((x*(1+ 6*x+4*x^2+2*x^3-x^4))/((-1+x)^4*(1+x)^2) + O(x^50)) \\ Colin Barker, Jun 23 2015; Michel Marcus, Jan 19 2019

Formula

From Emeric Deutsch, Sep 16 2010: (Start)

a(2n+1) = (2n+1)(2n^2+4*n+1); a(2n)=4n^2*(n+1).

G.f.: (z (1 + 6 z + 4 z^2 + 2 z^3 - z^4))/((-1 + z)^4 (1 + z)^2).

(End)

a(n) = 2*a(n-1) + a(n-2) - 4*a(n-3) + a(n-4) + 2*a(n-5) - a(n-6).

Extensions

a(1)-a(2) from Eric W. Weisstein, Sep 08 2017