The possible cardinalities of global secure sets in cographs
Let G = (V, E) be a graph. A global secure set SD subset of V is a dominating set which also satisfies a condition that vertical bar N [X] boolean AND SD vertical bar >= vertical bar N [X] - SD vertical bar for every subset X subset of SD. The minimum cardinality of the global secure set in the graph G is denoted by gamma(s)(G). In this paper, we introduce the notion of gamma(s)-monotone graphs. The graph G is gamma(s)-monotone if, for every k is an element of {gamma(s)(G), gamma(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. (C) 2011 Elsevier B.V. All rights reserved.
secure set cograph graph dominating set alliance cotree