Autor segons l'article: Dettlaff, M.; Lemanska, M.; Rodriguez-Velazquez, J. A.;
Departament: Enginyeria Informàtica i Matemàtiques
Autor/s de la URV: Rodríguez Velázquez, Juan Alberto
Paraules clau: Secure italian domination Secure domination number Roman Protection Np-hard Minimum weight Italian domination Graph theory Graph g Domination number Domination in graphs Dominating function Adjacent vertices
Resum: 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., Sigma(u is an element of G(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 f(u -> v) is defined by f(u -> v)(v) = 1, f(u -> v)(u) = f (u) - 1 and f(u -> v)(x) = f ( x) whenever x is an element of 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 f(u -> v) is an IDF. The weight of f is.( f) = Sigma(v is an element of 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.
Àrees temàtiques: Mathematics, applied Interdisciplinar Engenharias iii Discrete mathematics and combinatorics Control and optimization Computer science, interdisciplinary applications Computer science applications Computational theory and mathematics Ciência da computação Applied mathematics
Accès a la llicència d'ús: https://creativecommons.org/licenses/by/3.0/es/
Adreça de correu electrònic de l'autor: juanalberto.rodriguez@urv.cat
Identificador de l'autor: 0000-0002-9082-7647
Data d'alta del registre: 2023-02-19
Versió de l'article dipositat: info:eu-repo/semantics/publishedVersion
Enllaç font original: https://link.springer.com/article/10.1007/s10878-020-00658-1
URL Document de llicència: http://repositori.urv.cat/ca/proteccio-de-dades/
Referència a l'article segons font original: Journal Of Combinatorial Optimization. 41 (1): 56-72
Referència de l'ítem segons les normes APA: Dettlaff, M.; Lemanska, M.; Rodriguez-Velazquez, J. A.; (2021). Secure Italian domination in graphs. Journal Of Combinatorial Optimization, 41(1), 56-72. DOI: 10.1007/s10878-020-00658-1
DOI de l'article: 10.1007/s10878-020-00658-1
Entitat: Universitat Rovira i Virgili
Any de publicació de la revista: 2021
Tipus de publicació: Journal Publications
Repositori URV