The cost of edge failure with respect to secure graph domination

Abstract

A subset V₁ of the vertex set of a graph G is a secure dominating set of G if V₁ is a dominating set of G and if, for each vertex u not in V₁, there is a neighbouring vertex v of u in V₁ such that the swap set V₁\{v} U {u} is again a dominating set of G. The secure domination number of G, denoted by γ_a(G), is the cardinality of a smallest secure dominating set of G. In this paper we consider two cost functions, c_q{G) and C_q(G), which measure respectively the smallest possible and the largest possible increase in the cardinality of a secure dominating set, over and above γ_a(G), if q edges were to be removed from G. We establish bounds on c_q(G) and C_q(G) for a general graph G and go on to sharpen these bounds or determine these parameters exactly for a number of special graph classes, including paths, cycles, complete graphs and complete bipartite graphs.