Upper Secure Domination Number of a Graph

Abstract A subset S of V is a dominating set of a graph G = ( V , E ) if every vertex in V \ S is adjacent to a vertex in S . A dominating set S is called a secure dominating set if for each v ∈ V \ S there exists u ∈ S such that v is adjacent to u and S 1 = ( S − { u } ) ∪ { v } is a dominating set. The maximum cardinality of a minimal secure dominating set of G is called the upper secure domination number of G and is denoted by Γ s ( G ) . In this paper we initiate a study of this parameter and present several basic results.