Article ID Journal Published Year Pages File Type
1141490 Discrete Optimization 2015 12 Pages PDF
Abstract

A subset XX of the vertex set of a graph GG is a secure dominating set   of GG if XX is a dominating set of GG and if, for each vertex uu not in XX, there is a neighbouring vertex vv of uu in XX such that the swap set X−{v}∪{u}X−{v}∪{u} is again a dominating set of GG. The secure domination number   of GG is the cardinality of a smallest secure dominating set of GG. A graph GG is qq-critical   if the smallest arbitrary subset of edges whose removal from GG necessarily increases the secure domination number, has cardinality qq. In this paper we characterise qq-critical graphs for all admissible values of qq and determine the exact values of qq for which members of various infinite classes of graphs are qq-critical.

Related Topics
Physical Sciences and Engineering Mathematics Control and Optimization
Authors
, , ,