Predavateljica: Nina Schmuck (TU Graz, Avstrija)
The extremal questions of maximising or minimising various distance-based graph invariants among trees with a given degree sequence have been vigorously studied. In many cases, the so-called greedy tree and some caterpillars are found to be extremal. Therefore, the following question naturally arises: What do the distance-based graph invariants look like when the optimal solution of the minimisation problem is the greedy tree and, analogously, when the optimal solution of the maximisation problem is a caterpillar.
We obtain that the greedy tree is optimal for all graph invariants of the form [W_f(T) = sum_{{u,v} subseteq V(T)} f(d(u,v))], for any nonnegative, nondecreasing function $f$. Furthermore, if $f$ is any increasing, convex function, we find that $W_f(T)$ is maximised by a caterpillar. From this result, we also achieve a partial characterisation of the structure of the extremal caterpillars.
Additionally, our solutions of both the minimisation and the maximisation problems include not only the classical Wiener index ($f(x)=x$), but also the hyper-Wiener index ($f(x)=frac{x(x+1)}{2}$) and the generalised Wiener index ($f(x)=x^{alpha}$ with $alpha > 1$).
Joint work with Stephan Wagner and Hua Wang.
