Extremal trees with fixed degree sequence (Q2223451)

For a given degree sequence \(D\) there are many graph invariants for which the greedy tree \({\mathcal{G}}(D)\) or the \(\mathcal{M}\)-tree \({\mathcal{M}}(D)\) is extremal. In this paper, the authors are focused in investigating properties satisfied by invariants for which \({\mathcal{G}}(D)\) or \({\mathcal{M}}(D)\) is extremal among all trees having a degree sequence \(D\). They present a general result that describes properties of invariants whose only extremal tree having degree sequence \(D\) is \({\mathcal{G}}(D)\) and analogously for \({\mathcal{M}}(D)\). With this result they are able to prove the following known results about invariants with extremal trees \({\mathcal{G}}(D)\) or \({\mathcal{M}}(D)\) for fixed degree sequence \(D\). For a given degree sequence \(D\) of a tree (1) \({\mathcal{G}}(D)\) is the unique tree that maximizes the number of subtrees; (2) a tree that minimizes Wiener index is a greedy tree \({\mathcal{G}}(D)\); (3) a tree that minimizes the Hosoya index is an \(\mathcal{M}\)-tree \({\mathcal{M}}(D)\); (4) the number of independent sets is maximized by \({\mathcal{M}}(D)\). The same general result is used to find some new invariants for which \({\mathcal{G}}(D)\) or \({\mathcal{M}}(D)\) is extremal tree with a degree sequence \(D\). These invariants are the number of rooted spanning forests (which is minimized by \({\mathcal{G}}(D)\)), the incidence energy (which is minimized by \({\mathcal{G}}(D)\)), Steiner \(r\)-Wiener index (minimized by \({\mathcal{G}}(D)\)) and the solvability (minimized by \({\mathcal{M}}(D)\)). Finally, they study trees whose degree sequence is majorised by a given degree sequence \(D\). They present many graph invariants for which extremal trees with degree sequence \(D\) are also extremal among those having a degree sequence \(B\) that is majorised by \(D\). Such invariants are the Wiener index, the number of subtrees, the weighted number of rooted spanning forests, the Hosoya index, the number of independent sets and the solvability.