A349703 -id:A349703 - cp's OEIS frontend

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

Kevin Ryde, Nov 26 2021

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.

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).

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

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);

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).

A349702 Irregular triangle read by rows where T(n,k) is the maximum terminal Wiener index for a tree of n vertices among which k are leaves.

Original entry on oeis.org

0, 0, 1, 2, 3, 6, 4, 8, 12, 5, 10, 16, 20, 6, 12, 20, 26, 30, 7, 14, 24, 32, 39, 42, 8, 16, 28, 38, 48, 54, 56, 9, 18, 32, 44, 57, 66, 72, 72, 10, 20, 36, 50, 66, 78, 88, 92, 90, 11, 22, 40, 56, 75, 90, 104, 112, 115, 110, 12, 24, 44, 62, 84, 102, 120, 132, 140, 140, 132

Offset: 0

Kevin Ryde, Nov 26 2021

Gutman, Furtula, and Petrović, define the terminal Wiener index as the sum of the distances between all pairs of leaves (pendant vertices, degree 1) in a tree (or graph).
They determine the maximum terminal Wiener index T(n,k), and construct the trees which attain this maximum.
The triangle rows are all possible n,k combinations, which means k=n in rows n=0..2, and k=2..n-1 in rows n>=3.
The maximum within row n is A349704(n) and for n >= 8 this occurs at kmax = floor(2*n/3)+2 = A004523(n)+2 and equal maximum at kmax+1 when n == 1 (mod 3).

			Triangle begins:
      k=0  1  2   3   4   5   6   7   8
  n=0;  0,
  n=1;     0,
  n=2;        1,
  n=3;        2,
  n=4;        3,  6,
  n=5;        4,  8, 12,
  n=6;        5, 10, 16, 20,
  n=7;        6, 12, 20, 26, 30,
  n=8;        7, 14, 24, 32, 39, 42,
  n=9;        8, 16, 28, 38, 48, 54, 56,

Kevin Ryde, Table of n, a(n) for n = 0..7023 (rows 0..120)
Ivan Gutman, Boris Furtula and Miroslav Petrović, Terminal Wiener Index, Journal of Mathematical Chemistry, volume 46, 2009, pages 522-531.

Cf. A349703 (number of trees), A349704 (row maxima).

T(n,k) = (((n-k+3)*k - 4)*k + if(k%2,k-n+1))>>2;

T(n,k) = k*(k-1) + (n-1-k)*floor(k/2)*ceiling(k/2). [Gutman, Furtula, Petrović, theorem 4]

G.f.: x^2*y^2*( 1 + x*(1 + (1-x)*(1+2*x*y)) / ((1-x)^2 * (1+x*y) * (1-x*y)^3) ).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula