Reducing the maximum degree of a graph by deleting vertices: the extremal cases

Abstract

Let $\lambda(G)$ denote 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. In a recent paper, we proved that if $n$ is the number of vertices of $G$, $k$ is the maximum degree of $G$, and $t$ is the number of vertices of degree $k$, then $\lambda (G) \leq \frac{n+(k-1)t}{2k}$. We also showed that $\lambda (G) \leq \frac{n}{k+1}$ if $G$ is a tree. In this paper, we provide a new proof of the first bound and use it to determine the graphs that attain the bound, and we also determine the trees that attain the second bound.

Keywords

• domination
• maximum degree
• vertex deletion