Wyszukiwarka
Abstrakt
An Italian dominating function (IDF) on a graph G is a function f:V(G)→{0,1,2} such that for every vertex v with f(v)=0, the total weight of f assigned to the neighbours of v is at least two, i.e., ∑u∈NG(v)f(u)≥2. For any function f:V(G)→{0,1,2} and any pair of adjacent vertices with f(v)=0 and u with f(u)>0, the function fu→v is defined by fu→v(v)=1, fu→v(u)=f(u)−1 and fu→v(x)=f(x) whenever x∈V(G)∖{u,v}. A secure Italian dominating function on a graph G is defined as an IDF f which satisfies that for every vertex v with f(v)=0, there exists a neighbour u with f(u)>0 such that fu→v is an IDF. The weight of f is ω(f)=∑v∈V(G)f(v). The minimum weight among all secure Italian dominating functions on G is the secure Italian domination number of G. This paper is devoted to initiating the study of the secure Italian domination number of a graph. In particular, we prove that the problem of finding this parameter is NP-hard and we obtain general bounds on it. Moreover, for certain classes of graphs, we obtain closed formulas for this novel parameter.
Cytowania
-
4
CrossRef
-
0
Web of Science
-
5
Scopus
Autorzy (3)
-
Juan A. RODRíGUEZ-VELáZQUEZ
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach
- Opublikowano w:
-
JOURNAL OF COMBINATORIAL OPTIMIZATION
nr 41,
strony 56 - 72,
ISSN: 1382-6905 - Język:
- angielski
- Rok wydania:
- 2021
- Opis bibliograficzny:
- Dettlaff M., Lemańska M., Rodríguez-Velázquez J.: Secure Italian domination in graphs// JOURNAL OF COMBINATORIAL OPTIMIZATION -Vol. 41, (2021), s.56-72
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s10878-020-00658-1
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 166 razy
Publikacje, które mogą cię zainteresować
The convex domination subdivision number of a graph
- M. Dettlaff,
- M. Lemańska,
- S. Kosary
- + 1 autorów