Spreads of degrees in graphs

Source abstract

For a graph $G$ and a set $B\subseteq V(G)$, the spread $\mathrm{sp}(B)$ of $B$ is the difference between the largest and the smallest degree in $G$ of a vertex of $B$, and for an integer $k\geq0$ the parameter $\mathrm{sp}(G,k)$ is the largest cardinality of a set $B$ with $\mathrm{sp}(B)\leq k$. Caro, Lauri and Zarb derived a lower bound for $\mathrm{sp}(G,k)$ and, among several families of graphs, considered $$\mathrm{MOP}(n,k)=\min \{\mathrm{sp}(G,k):G\text{ is a maximal outerplanar graph of order }n\}$$ and determined $\mathrm{MOP}(n,k)$ up to an additive constant for every $k\not =2,$ leaving the case $k=2$ open, with the bounds $4n/9\leq \mathrm{MOP}(n,2)\leq (5n+19)/11$. We first prove a lower bound on $\mathrm{sp}(G,k)$ for an arbitrary graph $G$ in terms of its order $n$, its number of edges $m$ and its minimum degree $δ$. This lower bound contains the bounds of Caro, Lauri and Zarb and, for $k=0$, the bound $\mathrm{rep}(G)\geq \left\lceil n/(2d-2δ+1)\right\rceil$ of Caro and West, where $d=2m/n$. We determine when this lower bound is attained, exhibit explicit graphs attaining it, and show that it is exact for all graphs once $n\geq n_{0}(δ,k,d)$. We then apply the bound to maximal outerplanar graphs: adjusting the count to this class we prove $$\mathrm{MOP}(n,2)\geq \left\lceil \frac{4n+10}{9}\right\rceil \qquad \text{for every }n\geq 14,$$ with equality for $n\equiv 2\ (\mathrm{mod}\ 18)$, and $\mathrm{MOP}(n,2)=4n/9+O(1)$ for every $n$.