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

Secure Italian domination in graphs

  • Datos identificativos

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

    Autor según el artículo: Dettlaff, M; Lemanska, M; Rodriguez-Velazquez, J A
    Departamento: Enginyeria Informàtica i Matemàtiques
    Autor/es de la URV: Rodríguez Velázquez, Juan Alberto
    Palabras clave: 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
    Resumen: 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.
    Áreas temáticas: 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
    Acceso a la licencia de uso: https://creativecommons.org/licenses/by/3.0/es/
    Direcció de correo del autor: juanalberto.rodriguez@urv.cat
    Identificador del autor: 0000-0002-9082-7647
    Fecha de alta del registro: 2024-10-26
    Versión del articulo depositado: info:eu-repo/semantics/publishedVersion
    Enlace a la fuente original: https://link.springer.com/article/10.1007/s10878-020-00658-1
    URL Documento de licencia: https://repositori.urv.cat/ca/proteccio-de-dades/
    Referencia al articulo segun fuente origial: Journal Of Combinatorial Optimization. 41 (1): 56-72
    Referencia 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 del artículo: 10.1007/s10878-020-00658-1
    Entidad: Universitat Rovira i Virgili
    Año de publicación de la revista: 2021
    Tipo de publicación: Journal Publications
  • Palabras clave:

    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
  • Documentos:

  • Cerca a google

    Search to google scholar