Reducing the maximum degree of a graph: comparisons of bounds

Let $\lambda(G)$ be the smallest number of vertices that can be removed from a non-empty graph $G$ so that the resulting graph has a smaller maximum degree. Let $\lambda_{\rm e}(G)$ be the smallest number of edges that can be removed from $G$ for the same purpose. Let $k$ be the maximum degree of $G$, let $t$ be the number of vertices of degree $k$, let $M(G)$ be the set of vertices of degree $k$, let $n$ be the number of vertices in the closed neighbourhood of $M(G)$, and let $m$ be the number of edges that have at least one vertex in $M(G)$. Fenech and the author showed that $\lambda(G) \leq \frac{n+(k-1)t}{2k}$, and they essentially showed that $\lambda (G) \leq n \left ( 1- \frac{k}{k+1} { \Big( \frac{n}{(k+1)t} \Big) }^{1/k} \right )$. They also showed that $\lambda_{\rm e}(G) \leq \frac{m + (k-1)t}{2k-1}$ and that if $k \geq 2$, then $\lambda_{\rm e} (G) \leq m \left ( 1- \frac{k-1}{k} { \Big( \frac{m}{kt} \Big) }^{1/(k-1)} \right )$. These bounds are attained if $G$ is the union of pairwise vertex-disjoint $(k+1)$-vertex stars. In this paper, we determine the cases in which one bound on $\lambda(G)$ is better than the other, and we show that the first bound on $\lambda_{\rm e}(G)$ is better than the second. This work is motivated by the likelihood that similar pairs of bounds will be discovered for other graph parameters and the same analysis can be applied