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

Abstrakt

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.

Cytowania

0

CrossRef
0

Web of Science
0

Scopus

Autorzy (4)

Abel Cabrera-Martinez PhD
Magda Dettlaff dr inż.
- Wydział Fizyki Technicznej i Matematyki Stosowanej
- Politechnika Gdańska
Magdalena Lemańska dr inż.
- Wydział Fizyki Technicznej i Matematyki Stosowanej
- Politechnika Gdańska
Juan Alberto Rodriguez-Velazquez Prof

Cytuj jako

Pełna treść

pobierz publikację

pobrano 13 razy

Wersja publikacji: Accepted albo Published Version
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7151/dmgt.2532
Licencja: otwiera się w nowej karcie

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

DIFFERENTIALS IN GRAPHS, RESTRAINED DIFFERENTIAL, RESTRAINED ROMAN DOMINATION

Informacje szczegółowe

Kategoria:

Publikacja w czasopiśmie

Typ:

artykuły w czasopismach

Opublikowano w:

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

Język:

angielski

Rok wydania:

2023

Opis bibliograficzny:

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: