Largest Domination Number and Smallest Independence Number of Forests with given Degree Sequence

Abstract

For a sequence $d$ of non-negative integers, let $\mathcal{F}(d)$ be the set of all forests whose degree sequence is $d$. We present closed formulas for ${\gamma }_{\max }^{\mathcal{F}}(d)=\max \{\gamma (F):F\in \mathcal{F}(d)\}$ and ${\alpha }_{\min }^{\mathcal{F}}(d)=\min \{\alpha (F):F\in \mathcal{F}(d)\}$ where $\gamma (F)$ and $\alpha (F)$ are the domination number and the independence number of a forest $F$, respectively.