Publications Repository - Gdańsk University of Technology

Given a graph $G=(V(G), E(G))$ and a vertex $v\in V(G)$, the {open neighbourhood} of $v$ is defined to be $N(v)=\{u\in V(G) :\, uv\in E(G)\}$. The {external neighbourhood} of a set $S\subseteq V(G)$ is defined as $S_e=\left(\cup_{v\in S}N(v)\right)\setminus S$, while the \emph{restrained external neighbourhood} of $S$ is defined as $S_r=\{v\in S_e : N(v)\cap S_e\neq \varnothing\}$. The restrained differential of a graph $G$ is defined as $\partial_r(G)=\max \{|S_r|-|S|:\, S\subseteq 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.

Authors

• PhD Abel Cabrera-Martinez,
• dr inż. Magda Dettlaff link open in new tab ,
• dr inż. Magdalena Lemańska link open in new tab ,
• Prof Juan Alberto Rodriguez-Velazquez