A192032 Square array read by antidiagonals: W(m,n) (m >= 0, n >= 0) is the Wiener index of the graph G(m,n) obtained in the following way: connect by an edge the center of an m-edge star with the center of an n-edge star. The Wiener index of a connected graph is the sum of distances between all unordered pairs of vertices in the graph.

1, 4, 4, 9, 10, 9, 16, 18, 18, 16, 25, 28, 29, 28, 25, 36, 40, 42, 42, 40, 36, 49, 54, 57, 58, 57, 54, 49, 64, 70, 74, 76, 76, 74, 70, 64, 81, 88, 93, 96, 97, 96, 93, 88, 81, 100, 108, 114, 118, 120, 120, 118, 114, 108, 100, 121, 130, 137, 142, 145, 146, 145, 142, 137, 130, 121

Offset: 0

Author

Emeric Deutsch, Jun 30 2011

Keywords

• nonn
• tabl

Comments

W(n,0) = W(0,n) = A000290(n+1) = (n+1)^2.

W(n,1) = W(1,n) = A028552(n+1) = (n+1)*(n+4).

W(n,2) = W(2,n) = A028881(n+4) = n^2 + 8*n + 9.

W(n,n) = A079273(n+1) = 5*n^2 + 4*n + 1.

W(n,m) = W(m,n) (trivially).

Examples

			W(1,2)=18 because in the graph with vertex set {A,a,B,b,b'} and edge set {AB, Aa, Bb, Bb'} we have 4 pairs of vertices at distance 1 (the edges), 4 pairs at distance 2 (Ab, Ab', Ba, bb') and 2 pairs at distance 3 (ab,ab'); 4*1 + 4*2 + 2*3 = 18.
The square array starts:
   1,  4,  9, 16, 25, ...;
   4, 10, 18, 28, 30, ...;
   9, 18, 29, 42, 57, ...;
  16, 28, 42, 58, 76, ...;
		

Links

• B. E. Sagan, Y-N. Yeh and P. Zhang, The Wiener Polynomial of a Graph, Internat. J. of Quantum Chem., 60, 1996, 959-969.

Crossrefs

Cf. A000290, A028552, A028881, A079273.

Programs

Maple

W := proc (m, n) options operator, arrow: m^2+n^2+3*m*n+2*m+2*n+1 end proc: for n from 0 to 10 do seq(W(n-i, i), i = 0 .. n) end do; # yields the antidiagonals in triangular form
W := proc (m, n) options operator, arrow: m^2+n^2+3*m*n+2*m+2*n+1 end proc: for m from 0 to 9 do seq(W(m, n), n = 0 .. 9) end do; # yields the first 10 entries of each of rows 0,1,2,...,9

Formula

W(m,n) = m^2 + n^2 + 3*m*n + 2*m + 2*n + 1.

The Wiener polynomial of the graph G(n,m) is P(m,n;t) = (m+n+1)*t + (1/2)*(m^2 + n^2 + m + n)*t^2 + m*n*t^3.