Secure domination in rooted product graphs
Rangel Hernández-Ortiz (),
Luis Pedro Montejano () and
Juan Alberto Rodríguez-Velázquez ()
Additional contact information
Rangel Hernández-Ortiz: Universidad Autónoma Metropolitana
Luis Pedro Montejano: Universitat Rovira i Virgili
Juan Alberto Rodríguez-Velázquez: Universitat Rovira i Virgili
Journal of Combinatorial Optimization, 2021, vol. 41, issue 2, No 8, 413 pages
Abstract:
Abstract A secure dominating set of a graph G is a dominating set S satisfying that for every vertex $$v\in V(G){\setminus } S$$ v ∈ V ( G ) \ S there exists a neighbour $$u\in S$$ u ∈ S of v such that $$(S\cup \{v\}){\setminus } \{u\}$$ ( S ∪ { v } ) \ { u } is a dominating set as well. The secure domination number, denoted by $$\gamma _s(G)$$ γ 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\circ _vH$$ G ∘ v H satisfies one of the following three formulas, $$\gamma _{s}(G\circ _vH)=n(G)(\gamma _{s}(H)-1)+\gamma (G)$$ γ s ( G ∘ v H ) = n ( G ) ( γ s ( H ) - 1 ) + γ ( G ) , $$\gamma _{s}(G\circ _vH)= n(G)(\gamma _{s}(H)-1)+\gamma _{s}(G)$$ γ s ( G ∘ v H ) = n ( G ) ( γ s ( H ) - 1 ) + γ s ( G ) or $$\gamma _{s}(G\circ _vH)= n(G)\gamma _{s}(H)$$ γ s ( G ∘ v H ) = n ( G ) γ s ( H ) , where $$\gamma (G)$$ γ ( 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.
Keywords: Secure domination; Rooted product graphs; Corona product graphs; 05C69; 05C76 (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:
Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00679-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:41:y:2021:i:2:d:10.1007_s10878-020-00679-w
Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878
DOI: 10.1007/s10878-020-00679-w
Access Statistics for this article
Journal of Combinatorial Optimization is currently edited by Thai, My T.
More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().