Autor según el artículo: Hernandez-Ortiz, Rangel; Montejano, Luis Pedro; Rodriguez-Velazquez, Juan Alberto;
Departamento: Enginyeria Informàtica i Matemàtiques
Autor/es de la URV: Hernández Ortiz, Rangel / Montejano Cantoral, Luis Pedro / Rodríguez Velázquez, Juan Alberto
Palabras clave: 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
Resumen: 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.
Á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: luispedro.montejano@urv.cat juanalberto.rodriguez@urv.cat
Identificador del autor: 0000-0002-9082-7647
Fecha de alta del registro: 2024-01-23
Versión del articulo depositado: info:eu-repo/semantics/acceptedVersion
Enlace a la fuente original: https://link.springer.com/article/10.1007/s10878-020-00679-w?noAccess=true
URL Documento de licencia: http://repositori.urv.cat/ca/proteccio-de-dades/
Referencia al articulo segun fuente origial: Journal Of Combinatorial Optimization. 41 (2): 401-413
Referencia 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 del artículo: 10.1007/s10878-020-00679-w
Entidad: Universitat Rovira i Virgili
Año de publicación de la revista: 2021
Tipo de publicación: Journal Publications
Repositori URV