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

Abstract

Let (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 (G) n+(k􀀀1)t 2k . We also showed that (G) 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.