Security, (F,I)-security, and Ultra-security in Graphs

Abstract

Let G=(V,E) be a graph and S a subset of V. The notion of security in graphs was first presented by Brigham et al [3]. A set S is secure if every attack on S is defendable. The cardinality of a smallest secure set of G is the security number of G. We give several new definitions of security. We show that some of these new definitions are equivalent to the definition given by Brigham et al, while others are not. In these new situations, we find necessary and sufficient conditions for security. Various Hall-type theorems are used in these proofs. We also define analogues of the security number and find them for various classes of graphs.