Article ID Journal Published Year Pages File Type
434890 Theoretical Computer Science 2012 9 Pages PDF
Abstract

Let G=(V,E) be a graph. A global secure set SD⊆V is a dominating set which also satisfies a condition that |N[X]∩SD|≥|N[X]−SD| for every subset X⊆SD. The minimum cardinality of the global secure set in the graph G is denoted by γs(G). In this paper, we introduce the notion of γs-monotone graphs. The graph G is γs-monotone if, for every k∈{γs(G),γs(G)+1,…,n}, it has a global secure set of cardinality k. We will also present the results concerning the minimum cardinality of the global secure sets in the class of cographs.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics