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

Secure domination in rooted product graphs

  • Dades identificatives

    Identificador: imarina:9228485
    Autors:
    Hernandez-Ortiz, RangelMontejano, Luis PedroRodriguez-Velazquez, Juan Alberto
    Resum:
    A secure dominating set of a graph G is a dominating set S satisfying that for every vertex v is an element of V(G)\S there exists a neighbour u is an element of S of v such that (S boolean OR {v})\{u} is a dominating set as well. The secure domination number, denoted by gamma(s) (G), is the minimum cardinality among all secure dominating sets of G. This concept was introduced in 2005 by Cockayne et al. and studied further in a number of works. The problem of computing the secure domination number is NP-Hard. This suggests finding the secure domination number for special classes of graphs or obtaining tight bounds on this invariant. The aim of this work is to obtain closed formulas for the secure domination number of rooted product graphs. We show that for any graph G of order n(G) and any graph H with root v, the secure domination number of the rooted product graph G. v H satisfies one of the following three formulas,gamma(s) (G o(nu) H) = n(G)(gamma(s)( H) - 1) + gamma (G), gamma(s)(G omicron(v) H) = n(G)(gamma(s) ( H) - 1) + gamma(s) (G) o(nu) gamma(s) (G o(nu) H) = n(G)gamma(s) (H), where gamma (G) denotes the domination number of G. We also characterize the graphs that satisfy each of these expressions. As a particular case of the study, we derive the corresponding results for corona graphs.
  • Altres:

    Autor segons l'article: Hernandez-Ortiz, Rangel; Montejano, Luis Pedro; Rodriguez-Velazquez, Juan Alberto
    Departament: Enginyeria Informàtica i Matemàtiques
    Autor/s de la URV: Hernández Ortiz, Rangel / Montejano Cantoral, Luis Pedro / Rodríguez Velázquez, Juan Alberto
    Paraules clau: Tight bound Special class Secure domination Rooted product graphs Protection Product graph Np-hard Graphic methods Graph theory Graph g Domination number Dominating sets Corona product graphs Cardinalities
    Resum: A secure dominating set of a graph G is a dominating set S satisfying that for every vertex v is an element of V(G)\S there exists a neighbour u is an element of S of v such that (S boolean OR {v})\{u} is a dominating set as well. The secure domination number, denoted by gamma(s) (G), is the minimum cardinality among all secure dominating sets of G. This concept was introduced in 2005 by Cockayne et al. and studied further in a number of works. The problem of computing the secure domination number is NP-Hard. This suggests finding the secure domination number for special classes of graphs or obtaining tight bounds on this invariant. The aim of this work is to obtain closed formulas for the secure domination number of rooted product graphs. We show that for any graph G of order n(G) and any graph H with root v, the secure domination number of the rooted product graph G. v H satisfies one of the following three formulas,gamma(s) (G o(nu) H) = n(G)(gamma(s)( H) - 1) + gamma (G), gamma(s)(G omicron(v) H) = n(G)(gamma(s) ( H) - 1) + gamma(s) (G) o(nu) gamma(s) (G o(nu) H) = n(G)gamma(s) (H), where gamma (G) denotes the domination number of G. We also characterize the graphs that satisfy each of these expressions. As a particular case of the study, we derive the corresponding results for corona graphs.
    À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: luispedro.montejano@urv.cat 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/acceptedVersion
    Enllaç font original: https://link.springer.com/article/10.1007/s10878-020-00679-w?noAccess=true
    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 (2): 401-413
    Referència de l'ítem segons les normes APA: Hernandez-Ortiz, Rangel; Montejano, Luis Pedro; Rodriguez-Velazquez, Juan Alberto (2021). Secure domination in rooted product graphs. Journal Of Combinatorial Optimization, 41(2), 401-413. DOI: 10.1007/s10878-020-00679-w
    DOI de l'article: 10.1007/s10878-020-00679-w
    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
    Tight bound
    Special class
    Secure domination
    Rooted product graphs
    Protection
    Product graph
    Np-hard
    Graphic methods
    Graph theory
    Graph g
    Domination number
    Dominating sets
    Corona product graphs
    Cardinalities
    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