|
|
A349704
|
|
Maximum terminal Wiener index for a tree of n vertices.
|
|
3
|
|
|
0, 0, 1, 2, 6, 12, 20, 30, 42, 56, 72, 92, 115, 140, 170, 204, 240, 282, 329, 378, 434, 496, 560, 632, 711, 792, 882, 980, 1080, 1190, 1309, 1430, 1562, 1704, 1848, 2004, 2171, 2340, 2522, 2716, 2912, 3122, 3345, 3570, 3810, 4064, 4320, 4592, 4879, 5168, 5474
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
Gutman, Furtula, and Petrović, define the terminal Wiener index as the sum of the distances between all pairs of pendant vertices (leaves, degree 1) in a tree (or graph).
They determine the maximum terminal Wiener index for trees of n vertices and construct the trees which attain this maximum.
For n<=9 the star-n uniquely attains the maximum, and beyond that there are certain cases according as n mod 3.
|
|
LINKS
|
Ivan Gutman, Boris Furtula and Miroslav Petrović, Terminal Wiener Index, Journal of Mathematical Chemistry, volume 46, 2009, pages 522-531.
|
|
FORMULA
|
a(0) = a(1) = a(2) = 1, a(n) = (n-1)*(n-2) for 3 <= n <= 9, and otherwise: [Gutman, Furtula, Petrović, theorem 5]
a(3s) = s^3 + 3*s^2 + s - 1,
a(3s+1) = s^3 + 4*s^2 + 3*s,
a(3s+2) = s^3 + 5*s^2 + 6*s + 2.
a(n) = 2*a(n-1) - a(n-2) + 2*a(n-3) - 4*a(n-4) + 2*a(n-5) - a(n-6) + 2*a(n-7) - a(n-8) for n>=15.
G.f.: 1 - x^2 - 2*x^3 - 2*x^4 - 2*x^5 - x^6 + (-1 + 2*x + x^2 + 2*x^3 - 2*x^4) / ((1-x)^4*(1+x+x^2)^2).
|
|
PROG
|
(PARI) a(n) = if(n<4, max(0, n-1), n<7, (n-1)*(n-2), (((n+9)*n + if(n%3, 6, 9))*n - 1)\27);
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|