On minimum secure dominating sets of graphs |
| |
| Authors: | A.P. Burger J.H. van Vuuren |
| |
| Affiliation: | 1. Department of Logistics, Stellenbosch University, Private Bag X1, Matieland, 7602, South Africa.;2. Department of Industrial Engineering, Stellenbosch University, Private Bag X1,Matieland, 7602, South Africa. |
| |
| 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, in which case v is called a defender. The secure domination number of G is the cardinality of a smallest secure dominating set of G. In this paper, we show that every graph of minimum degree at least 2 possesses a minimum secure dominating set in which all vertices are defenders. We also characterise the classes of graphs that have secure domination numbers 1, 2 and 3. |
| |
| Keywords: | 05C69 05C99 |
|
|
