### Edge stability in secure graph domination

*Alewyn Petrus Burger, Anton Pierre de Villiers, Jan Harm van Vuuren*

#### Abstract

A subset X of the vertex set of a graph G is
a

*secure dominating set*of G if X is a dominating set of G and if, for each vertex u not in X, there is a neighbouring vertex v of u in X such that the swap set (X-{v})∪{u} is again a dominating set of G. The*secure domination number*of G is the cardinality of a smallest secure dominating set of G. A graph G is p-*stable*if the largest arbitrary subset of edges whose removal from G does not increase the secure domination number of the resulting graph, has cardinality p. In this paper we study the problem of computing p-stable graphs for all admissible values of p and determine the exact values of p for which members of various infinite classes of graphs are p-stable. We also consider the problem of determining analytically the largest value ω_{n}of p for which a graph of order n can be p-stable. We conjecture that ω_{n}=n-2 and motivate this conjecture.Full Text: PDF PostScript