Some Comments on the Slater number

Abstract

Let $G$ be a graph with degree sequence $d_1\ge \dots \ge d_n$. Slater proposed $s\ell (G)=\min \{s:(d_1+1)+\cdots +(d_s+1)\ge n\}$ as a lower bound on the domination number $\gamma (G)$ of $G$. We show that deciding the equality of $\gamma (G)$ and $s\ell (G)$ for a given graph $G$ is NP-complete but that one can decide efficiently whether $\gamma (G)>s\ell (G)$ or $\gamma (G)\le \left(\lceil \ln \left(\frac{n(G)}{s\ell (G)}\right)\rceil +1\right)s\ell (G)$. For real numbers $\alpha$ and $\beta$ with $\alpha \ge \max \{0,\beta \}$, let $\mathcal{G}(\alpha ,\beta )$ be the class of non-null graphs $G$ such that every non-null subgraph $H$ of $G$ has at most $\alpha n(H)-\beta$ many edges. Generalizing a result of Desormeaux, Haynes, and Henning, we show that $\gamma (G)\le (2\alpha +1)s\ell (G)-2\beta$ for every graph $G$ in $\mathcal{G}(\alpha ,\beta )$ with $\alpha \le \frac{3}{2}$. Furthermore, we show that $\gamma (G)/s\ell (G)$ is bounded for graphs $G$ in $\mathcal{G}(\alpha ,\beta )$ if and only if $\alpha <2$. For an outerplanar graph $G$ with $s\ell (G)\ge 2$, we show $\gamma (G)\le 6s\ell (G)-6$. In analogy to $s\ell (G)$, we propose $s{\ell }_t(G)=\min \{s:d_1+\cdots +d_s\ge n\}$ as a lower bound on the total domination number. Strengthening results due to Raczek as well as Chellali and Haynes, we show that $s{\ell }_t(T)\ge \frac{n+2-n_1}{2}$ for every tree $T$ of order $n$ at least $2$ with $n_1$ endvertices.