A349704 Maximum terminal Wiener index for a tree of n vertices.

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

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

Kevin Ryde, Table of n, a(n) for n = 0..5000

Ivan Gutman, Boris Furtula and Miroslav Petrović, Terminal Wiener Index, Journal of Mathematical Chemistry, volume 46, 2009, pages 522-531.

Index entries for linear recurrences with constant coefficients, signature (2,-1,2,-4,2,-1,2,-1).

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

Cf. A133188 (number of trees attaining), A349703 (maximum by leaves).

Sequence in context: A103505 A279019 A002378 * A005991 A266194 A194110

Adjacent sequences: A349701 A349702 A349703 * A349705 A349706 A349707

Keyword

easy,nonn

Author

Kevin Ryde, Nov 26 2021

Status

approved