login
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.
0

%I #10 Mar 29 2020 13:08:11

%S 1,4,4,9,10,9,16,18,18,16,25,28,29,28,25,36,40,42,42,40,36,49,54,57,

%T 58,57,54,49,64,70,74,76,76,74,70,64,81,88,93,96,97,96,93,88,81,100,

%U 108,114,118,120,120,118,114,108,100,121,130,137,142,145,146,145,142,137,130,121

%N 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.

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

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

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

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

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

%H B. E. Sagan, Y-N. Yeh and P. Zhang, <a href="http://users.math.msu.edu/users/sagan/Papers/Old/wpg-pub.pdf">The Wiener Polynomial of a Graph</a>, Internat. J. of Quantum Chem., 60, 1996, 959-969.

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

%F 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.

%e 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.

%e The square array starts:

%e 1, 4, 9, 16, 25, ...;

%e 4, 10, 18, 28, 30, ...;

%e 9, 18, 29, 42, 57, ...;

%e 16, 28, 42, 58, 76, ...;

%p 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

%p 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

%Y Cf. A000290, A028552, A028881, A079273.

%K nonn,tabl

%O 0,2

%A _Emeric Deutsch_, Jun 30 2011