login
Square array read by antidiagonals: W(n,m) (n >= 1, m >= 1) is the Wiener index of the graph G(n,m) obtained from the n-circuit graph by joining at each of its nodes a path with m nodes (n >= 1, m >= 1; if m=1, then the n-circuit is not modified).
0

%I #12 Mar 29 2020 13:08:27

%S 0,1,1,3,10,4,8,27,35,10,15,60,93,84,20,27,105,196,222,165,35,42,174,

%T 335,456,435,286,56,64,259,537,770,880,753,455,84,90,376,784,1212,

%U 1475,1508,1197,680,120,125,513,1112,1750,2295,2515,2380,1788,969,165

%N Square array read by antidiagonals: W(n,m) (n >= 1, m >= 1) is the Wiener index of the graph G(n,m) obtained from the n-circuit graph by joining at each of its nodes a path with m nodes (n >= 1, m >= 1; if m=1, then the n-circuit is not modified).

%C W(1,m) = A000292(m-1).

%C W(2,m) = A000447(m) = A000292(2m-2).

%C W(n,1) = A034828(n).

%C W(n,2) = A180574(n) (n >= 3).

%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(n,m) = (1/24)*n*m*(3*m*n^2 + 12*n*m^2 - 8*m^2 - 12*n*m + 12*m - 4) if n is even;

%F W(n,m) = (1/24)*n*m*(3*m*n^2 + 12*n*m^2 - 8*m^2 - 12*n*m + 9*m - 4) if n is odd.

%F The Wiener polynomial P(n,m;t) of the graph G(n,m) is given in the 3rd Maple program. It gives, for example, P(3,4) = 12*t + 12*t^2 + 12*t^3 + 12*t^4 + 9*t^5 + 6*t^6 + 3*t^7. Its derivative, evaluated at t=1, yields the corresponding Wiener index W(3,4)=222.

%e a(3,1)=27 because in the graph with vertex set {A,B,C,A',B',C'} and edge set {AB, BC, CA, AA', BB', CC'} we have 6 pairs of vertices at distance 1 (the edges), 6 pairs at distance 2 (A'B, A'C, B'A, B'C, C'A, C'B) and 3 pairs at distance 3 (A'B', B'C', C'A'); 6*1 + 6*2 + 3*3 = 27.

%e The square array starts:

%e 0, 1, 4, 10, 20, 35, 56, 84, ...;

%e 1, 10, 35, 84, 165, 286, 455, 680, ...;

%e 3, 27, 93, 222, 435, 753, 1197, 1788, ...;

%e 8, 60, 196, 456, 880, 1508, 2380, 3536, ...;

%p W := proc (n, m) if `mod`(n, 2) = 0 then (1/24)*n*m*(3*n^2*m+12*n*m^2-8*m^2-12*n*m+12*m-4) else (1/24)*n*m*(3*n^2*m+12*n*m^2-8*m^2-12*n*m+9*m-4) end if end proc: for n to 10 do seq(W(n-i, i+1), i = 0 .. n-1) end do; # yields the antidiagonals in triangular form

%p W := proc (n, m) if `mod`(n, 2) = 0 then (1/24)*n*m*(3*n^2*m+12*n*m^2-8*m^2-12*n*m+12*m-4) else (1/24)*n*m*(3*n^2*m+12*n*m^2-8*m^2-12*n*m+9*m-4) end if end proc: for n to 10 do seq(W(n, m), m = 1 .. 10) end do; # yields the first 10 entries of each of rows 1,2,...,10.

%p P := proc (n, m) if `mod`(n, 2) = 0 then sort(expand(simplify(n*t*(t^m-m*t+m-1)/(1-t)^2+(n*(sum(t^j, j = 1 .. (1/2)*n-1))+(1/2)*n*t^((1/2)*n))*(1-t^m)^2/(1-t)^2))) else sort(expand(simplify(n*t*(t^m-m*t+m-1)/(1-t)^2+n*(sum(t^j, j = 1 .. (1/2)*n-1/2))*(1-t^m)^2/(1-t)^2))) end if end proc: P(3, 4);

%Y Cf. A000292, A000447, A034828, A180574.

%K nonn,tabl

%O 1,4

%A _Emeric Deutsch_, Jun 27 2011