RESTRAINED DIFFERENTIAL OF A GRAPH

Identifier:  imarina:9351729

Handle: https://hdl.handle.net/20.500.11797/imarina9351729

Authors:  Cabrera-Martínez, A; Dettlaff, M; Lemanska, M; Rodríguez-Velázquez, JA

Abstract:
Given a graph G = (V (G), E(G)) and a vertex v E V (G), the open neighbourhood of v is defined to be N(v) = {u E V(G) : uv E E(G)}. The external neighbourhood of a set S C V(G) is defined as Se = (Sv is an element of S N(v)) \ S, while the restrained external neighbourhood of S is defined as Sr = {vE Se : N(v) n Se =6 0}. The restrained differential of a graph G is defined as partial differential r(G) = max{|Sr| - |S| : S C V(G)}. In this paper, we introduce the study of the restrained differential of a graph. We show that this novel parameter is perfectly integrated into the theory of domination in graphs. We prove a Gallai-type theorem which shows that the theory of restrained differentials can be applied to develop the theory of restrained Roman domination, and we also show that the problem of finding the restrained differential of a graph is NP-hard. The relationships between the restrained differential of a graph and other types of differentials are also studied. Finally, we obtain several bounds on the restrained differential of a graph and we discuss the tightness of these bounds.