Author, as appears in the article.: Dettlaff, M; Lemanska, M; Rodriguez-Velazquez, J A
Department: Enginyeria Informàtica i Matemàtiques
URV's Author/s: Rodríguez Velázquez, Juan Alberto
Keywords: 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
Abstract: 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.
Thematic Areas: 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
licence for use: https://creativecommons.org/licenses/by/3.0/es/
Author's mail: juanalberto.rodriguez@urv.cat
Author identifier: 0000-0002-9082-7647
Record's date: 2024-10-26
Papper version: info:eu-repo/semantics/publishedVersion
Link to the original source: https://link.springer.com/article/10.1007/s10878-020-00658-1
Licence document URL: https://repositori.urv.cat/ca/proteccio-de-dades/
Papper original source: Journal Of Combinatorial Optimization. 41 (1): 56-72
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
Article's DOI: 10.1007/s10878-020-00658-1
Entity: Universitat Rovira i Virgili
Journal publication year: 2021
Publication Type: Journal Publications