Reducing the maximum degree of a graph: comparisons of bounds

Abstract

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.

Keywords

• maximum degree
• extremal graph theory