login
A180858
Square array read by antidiagonals: T(p,n) is the Wiener index of the fan graph F(p,n) (p>=1, n>=1). F(p,n) is the graph obtained by placing an edge between each node of the empty graph on p nodes and each node of the path graph on n nodes.
0
1, 4, 3, 9, 7, 7, 16, 13, 12, 13, 25, 21, 19, 19, 21, 36, 31, 28, 27, 28, 31, 49, 43, 39, 37, 37, 39, 43, 64, 57, 52, 49, 48, 49, 52, 57, 81, 73, 67, 63, 61, 61, 63, 67, 73, 100, 91, 84, 79, 76, 75, 76, 79, 84, 91, 121, 111, 103, 97, 93, 91, 91, 93, 97, 103, 111, 144, 133, 124
OFFSET
1,2
COMMENTS
The Wiener index of a connected graph is the sum of distances between all unordered pairs of vertices in the graph.
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.
Eric Weisstein's World of Mathematics, Fan Graph.
FORMULA
T(p,n) = p(p-1)+(n-1)^2+pn.
T(1,n) = n^2-n+1 = A002061(n).
T(2,n) = n^2+3 = A117950(n).
The Wiener polynomial of the graph F(p,n) is (pn+n-1)t+(1/2)[p(p-1)+(n-1)(n-2)]t^2.
EXAMPLE
T(2,3)=12 because the corresponding fan graph is the wheel graph on 5 nodes OABCD, O being the center of the wheel. Its Wiener index = number of edges + |AC| +|BD| = 8+2+2=12.
Square array T(p,n) begins:
1, 3, 7, 13, 21, 31, 43,...
4, 7, 12, 19, 28, 39, 52, ...
9, 13, 19, 27, 37, 49, 63,...
16, 21, 28, 37, 48, 61, 76, ...
MAPLE
T := proc (p, n) options operator, arrow: p*(p-1)+(n-1)^2+p*n end proc: for i to 12 do seq(T(i+1-j, j), j = 1 .. i) end do; # yields sequence in triangular form
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Sep 24 2010
STATUS
approved