Extremal Values of Ratios: Distance Problems vs. Subtree Problems in Trees

Abstract

The authors discovered a dual behaviour of two tree indices, the Wiener index and the number of subtrees, for a number of extremal problems  [Discrete Appl. Math. 155 (3) 2006, 374-385;  Adv. Appl. Math. 34 (2005), 138-155]. Barefoot, Entringer and Székely [Discrete Appl. Math. 80 (1997), 37-56] determined extremal values of $\sigma_T(w)/\sigma_T(u)$,   $\sigma_T(w)/\sigma_T(v)$, $\sigma(T)/\sigma_T(v)$, and $\sigma(T)/\sigma_T(w)$, where $T$ is a tree on $n$ vertices, $v$ is in the centroid of the tree $T$, and $u,w$ are leaves in $T$.

In this paper  we test how far the negative correlation between distances and subtrees go if we look for the   extremal values of $F_T(w)/F_T(u)$, $F_T(w)/F_T(v)$, $F(T)/F_T(v)$, and $F(T)/F_T(w)$, where $T$ is a tree on $n$ vertices, $v$ is in the subtree core of the tree $T$, and $u,w$ are leaves in $T$-the complete analogue of  [Discrete Appl. Math. 80 (1997), 37-56], changing distances to the number of subtrees.  We include a number of open problems, shifting the interest towards the number of subtrees in graphs.