zbMATH — the first resource for mathematics

Greedy trees, caterpillars, and Wiener-type graph invariants. (English) Zbl 1289.05145
Summary: We show a “universal property” of the greedy tree with a given degree sequence, namely that the number of pairs of vertices whose distance is at most \(k\) is maximized by the greedy tree for all \(k\). This rather strong assertion immediately implies, and is equivalent to, the minimality of the greedy trees with respect to graph invariants of the form \(W_f(T)=\sum_{\{u,v\}\subseteq V(T)}f(d(u,v))\) for any nonnegative, nondecreasing function \(f\). With different choices of \(f\), one directly solves the minimization problems of distance-based graph invariants including the classical Wiener index, the Hyper-Wiener index and the generalized Wiener index. We also consider the maximization of some of such invariants among trees with a given degree sequence. These problems turned out to be more complicated. Analogous to the known case of the Wiener index, we show that \(W_f(T)\) is maximized by a caterpillar for any increasing and convex function \(f\). This result also leads to a partial characterization of the structure of the extremal caterpillars. Through a similar approach, the maximization problem of the terminal Wiener index is also addressed.

05C12 Distance in graphs
05C05 Trees