Decreasing the maximum degree of a graph

Abstract

For a non-empty graph G, let λ(G) be the smallest number of vertices that can be deleted from G so that the maximum degree of the resulting graph is smaller than the maximum degree ∆(G) of G. If G is regular, then λ(G) is the domination number γ(G) of G. We show that if 1 ≤ k < r and c is a real number such that γ(H) ≤ c|V (H)| for every connected k-regular graph H with |V (H)| ≥ r, then λ(G) ≤ c|V (G)| for every connected graph G with ∆(G) = k and |V (G)| ≥ r. We in fact show that λ(G) ≤ γ(H) / |V (H)| |V (G)| for an H explicitly constructed from G. Several bounds on λ(G) follow. Various problems motivated by the result are posed, and related results are obtained. We also provide a sharp bound on λ(G) that depends only on the vertices of largest degree. We call a vertex of largest degree a ∆-vertex. We call a ∆-vertex v solitary if no other ∆-vertex is of distance at most 2 from v. Let S(G) be the set of solitary ∆-vertices, and let T(G) be the set of non-solitary ∆-vertices. We show that λ(G) ≤ |S(G)| + ∆(G) / ∆(G) + 1|T(G)|. The bound can be attained with T(G) 6= ∅.