Wyszukiwarka
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
-
Juan Alberto Rodriguez-Velazquez Prof
Cytuj jako
Pełna treść
- 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
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach dostępnych w wersji elektronicznej [także online]
- Opublikowano w:
-
Discussiones Mathematicae Graph Theory
strony 1 - 20,
ISSN: 1234-3099 - Język:
- angielski
- Rok wydania:
- 2023
- Opis bibliograficzny:
- Cabrera-Martinez A., Dettlaff M., Lemańska M., Rodriguez-Velazquez J. A., Restrained differential of a graph, Discussiones Mathematicae Graph Theory, 2023,10.7151/dmgt.2532
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7151/dmgt.2532
- Źródła finansowania:
-
- Publikacja bezkosztowa
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 56 razy
Publikacje, które mogą cię zainteresować
On the super domination number of lexicographic product graphs
- M. Dettlaff,
- M. Lemańska,
- J. A. RODRíGUEZ-VELáZQUEZ
- + 1 autorów