|
Vertex Covers and Secure Domination in Graphs |
|---|
Alewyn P Burger1, Michael A Henning2 & Jan H van Vuuren3
Abstract
Let G = (V;E) be a graph and let S be a subset of V. The set S is a dominating set of G if every vertex not in S is adjacent to some vertex in S. The set S is a secure dominating set of G if for each u not in S, there exists a vertex v in S such that uv is an edge of G and S without v but together with u is a dominating set of G. The minimum cardinality of a secure dominating set of G is the secure domination number 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 the secure domination number of G is at most n/2. Furthermore, if the secure domination number of G equals n/2, then G has a perfect matching. Our proof uses a covering of a subset of V by vertex-disjoint copies of subgraphs each of which is isomorphic to K2 or to an odd cycle.
An electronic version of the complete paper may be obtained here: [pdf].
Affiliations
1 Department of Logistics, Stellenbosch University, Private Bag X1, Matieland, 7602, Republic of South Africa, email: apburger@sun.ac.za.
2 School of Mathematical Sciences, University of KwaZulu-Natal, Pietermaritzburg, 3209, Republic of South Africa, email: henning@ukzn.ac.za.
3 Department of Logistics, Stellenbosch University, Private Bag X1, Matieland, 7602, Republic of South Africa, email:
vuuren@sun.ac.za.