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

Secure Italian domination in graphs

  • Identification data

    Identifier: imarina:9048287
    Authors:
    Dettlaff, MLemanska, MRodriguez-Velazquez, J A
    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.
  • Others:

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

    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