Extremal values of ratios: distance problems vs. subtree problems in trees

László Székely¹ ; Hua Wang²

¹Department of Mathematics University of South Carolina
²Mathematical Sciences Georgia Southern University

The electronic journal of combinatorics, Tome 20 (2013) no. 1

Résumé

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.

Détail

DOI : 10.37236/3020

Classification : 05C05, 05C12, 05C35, 92E10
Mots-clés : Wiener index, binary tree, caterpillar, star tree, good binary tree, distances in trees, subtrees of trees, extremal problems, center, centroid, subtree core