Extremal trees with fixed degree sequence

is extremal. Many known results, for example on the Wiener index, the number of subtrees, the number of independent subsets and the number of matchings follow as corollaries, as do some new results on invariants such as the number of rooted spanning forests, the incidence energy and the solvability. We also extend our results on trees with fixed degree sequence

D

to the set of trees whose degree sequence is majorised by a given sequence

D

, which also has a number of applications.

Review text

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.

Recommendations

Cites work

Cited in

(20)

This page was built for publication: Extremal trees with fixed degree sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2223451)