The greedy tree $\mathcal{G}(D)$ and the $\mathcal{M}$-tree $\mathcal{M}(D)$ are known to be extremal among trees with degree sequence $D$ with respect to various graph invariants. This paper provides a general theorem that covers a large family of invariants for which $\mathcal{G}(D)$ or $\mathcal{M}(D)$ 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.
@article{10_37236_9770,
author = {Eric O. D. Andriantiana and Valisoa Razanajatovo Misanantenaina and Stephan Wagner},
title = {Extremal trees with fixed degree sequence},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {1},
doi = {10.37236/9770},
zbl = {1461.05030},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9770/}
}
TY - JOUR
AU - Eric O. D. Andriantiana
AU - Valisoa Razanajatovo Misanantenaina
AU - Stephan Wagner
TI - Extremal trees with fixed degree sequence
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/9770/
DO - 10.37236/9770
ID - 10_37236_9770
ER -
%0 Journal Article
%A Eric O. D. Andriantiana
%A Valisoa Razanajatovo Misanantenaina
%A Stephan Wagner
%T Extremal trees with fixed degree sequence
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/9770/
%R 10.37236/9770
%F 10_37236_9770
Eric O. D. Andriantiana; Valisoa Razanajatovo Misanantenaina; Stephan Wagner. Extremal trees with fixed degree sequence. The electronic journal of combinatorics, Tome 28 (2021) no. 1. doi: 10.37236/9770
