Restrained differential of a graph

Abel Cabrera-Martinez; Magda Dettlaff; Magdalena Lemańska; Juan Alberto Rodriguez-Velazquez

doi:10.7151/dmgt.2532

Restrained differential of a graph

Abstract

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.

Citations

0

CrossRef
0

Web of Science
0

Scopus

Authors (4)

Abel Cabrera-Martinez PhD
Magda Dettlaff dr inż.
- Faculty of Applied Physics and Mathematics
- Gdańsk University of Technology
Magdalena Lemańska dr inż.
- Faculty of Applied Physics and Mathematics
- Gdańsk University of Technology
Juan Alberto Rodriguez-Velazquez Prof

Cite as

Full text

download paper

downloaded 13 times

Publication version: Accepted or Published Version
DOI:: Digital Object Identifier (open in new tab) 10.7151/dmgt.2532
License: open in new tab

full content of the article see on external site open in new tab

Keywords

DIFFERENTIALS IN GRAPHS, RESTRAINED DIFFERENTIAL, RESTRAINED ROMAN DOMINATION

Details

Category:

Articles

Type:

artykuły w czasopismach

Published in:

Discussiones Mathematicae Graph Theory pages 1 - 20,
ISSN: 1234-3099

Language:

English

Publication year:

2023

Bibliographic description:

Lemańska M., Dettlaff M., Cabrera-Martinez A., Rodriguez-Velazquez J. A.: Restrained differential of a graph// Discussiones Mathematicae Graph Theory -, (2023), s.1-20

DOI: