论文标题
具有固定度序列的极端树木
Extremal trees with fixed degree sequence
论文作者
论文摘要
贪婪的树$ \ Mathcal {g}（d）$和$ \ Mathcal {M} $ - 树$ \ Mathcal {M}（M}（D）$在具有序列$ D $的树中是极端的，相对于各种图形不变。本文提供了一般定理，该定理涵盖了一个大型不变的家族，其中$ \ MATHCAL {g}（d）$或$ \ MATHCAL {M}（M}（d）$是极端的。许多已知的结果，例如在维也纳指数上，子树的数量，独立子集的数量以及匹配的数量作为基冠的次数，以及对不变性的一些新结果，例如生根的跨越森林的数量，发病率的能量和溶解度。我们还将结果扩展到具有固定度序列$ d $的树木上的树木，其学位序列由给定序列$ d $进行专业，该序列还具有许多应用。
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.
