cp's OEIS Frontend

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.

%I A349702 #13 Nov 28 2021 01:20:15
%S A349702 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,
%T A349702 38,48,54,56,9,18,32,44,57,66,72,72,10,20,36,50,66,78,88,92,90,11,22,
%U A349702 40,56,75,90,104,112,115,110,12,24,44,62,84,102,120,132,140,140,132
%N 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.
%C A349702 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).
%C A349702 They determine the maximum terminal Wiener index T(n,k), and construct the trees which attain this maximum.
%C A349702 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.
%C A349702 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).
%H A349702 Kevin Ryde, <a href="/A349702/b349702.txt">Table of n, a(n) for n = 0..7023</a> (rows 0..120)
%H A349702 Ivan Gutman, Boris Furtula and Miroslav Petrović, <a href="https://doi.org/10.1007/s10910-008-9476-2">Terminal Wiener Index</a>, Journal of Mathematical Chemistry, volume 46, 2009, pages 522-531.
%F A349702 T(n,k) = k*(k-1) + (n-1-k)*floor(k/2)*ceiling(k/2). [Gutman, Furtula, Petrović, theorem 4]
%F A349702 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) ).
%e A349702 Triangle begins:
%e A349702       k=0  1  2   3   4   5   6   7   8
%e A349702   n=0;  0,
%e A349702   n=1;     0,
%e A349702   n=2;        1,
%e A349702   n=3;        2,
%e A349702   n=4;        3,  6,
%e A349702   n=5;        4,  8, 12,
%e A349702   n=6;        5, 10, 16, 20,
%e A349702   n=7;        6, 12, 20, 26, 30,
%e A349702   n=8;        7, 14, 24, 32, 39, 42,
%e A349702   n=9;        8, 16, 28, 38, 48, 54, 56,
%o A349702 (PARI) T(n,k) = (((n-k+3)*k - 4)*k + if(k%2,k-n+1))>>2;
%Y A349702 Cf. A349703 (number of trees), A349704 (row maxima).
%K A349702 easy,nonn,tabf
%O A349702 0,4
%A A349702 _Kevin Ryde_, Nov 26 2021