Vertex Covers and Secure Domination in Graphs

Abstract

Let G = (V,E) be a graph and let S ⊆ V. The set S is a dominating set of G if every vertex in V \\S is adjacent to some vertex in S. The set S is a secure dominating set of G if for each u ∈ V \\S, there exists a vertex v ∈ S such that uv ∈ E and (S \\{v})∪{u} is a dominating set of G. The minimum cardinality of a secure dominating set in G is the secure domination number γs(G) of G. We show that if G is a connected graph of order n with minimum degree at least two that is not a 5-cycle, then γs(G) ≤ n/2. Furthermore if γs(G) = n/2, then G has a perfect matching. Our proof uses a covering of a subset of V (G) by vertex-disjoint copies of subgraphs each of which is isomorphic to K2 or to an odd cycle.