Bounds on the differential of a graph

Abstract

Let G = (V, E) be a graph of order n and size m. Let B(D) be the set of vertices in V \ D that have a neighbor in the set D. The differential of a set D is defined as d(D) = \B{D)\ - |D| and the differential of a graph to equal the maximum value of d(D) for any subset D of V. In this paper we obtain several tight bounds for the differential of a graph. In particular, we relate the differential of a graph with known parameters of a graph, namely, its order, size, minimum and maximum degree, its girth, its domination number, its 2-domination number, its 2-packing number and its independence number.