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

##### MSC:
 05C12 Distance in graphs 05C05 Trees