login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
Cf. A133188 (number of trees attaining), A349703 (maximum by leaves).
Sequence in context: A103505 A279019 A002378 * A005991 A266194 A194110
KEYWORD
easy,nonn
AUTHOR
Kevin Ryde, Nov 26 2021
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 01:36 EDT 2024. Contains 371264 sequences. (Running on oeis4.)