Bounds on the differential of a graph - Basilio, Ludwin A.; Bermudo, Sergio; Sigarreta, José M. (Utilitas Mathematica, 2017)
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) = 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.