Theory and Applications of Graphs Theory and Applications of Graphs

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 2 k . We also showed that λ ( G ) ≤ nk +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.