Articles producció científica> Enginyeria Informàtica i Matemàtiques

Secure Italian domination in graphs

  • Dades identificatives

    Identificador: imarina:9048287
    Autors:
    Dettlaff, MLemanska, MRodriguez-Velazquez, J A
    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.
  • Altres:

    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: 2024-10-26
    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: https://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
  • Paraules clau:

    Applied Mathematics,Computational Theory and Mathematics,Computer Science Applications,Computer Science, Interdisciplinary Applications,Control and Optimization,Discrete Mathematics and Combinatorics,Mathematics, Applied
    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
    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
  • Documents:

  • Cerca a google

    Search to google scholar