## 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 and this bound is sharp. Our proof uses a covering of a subset of V(G) by vertex-disjoint copies of subgraphs each of which is isomorphic to K_{2} or to an odd cycle.

Original language | English |
---|---|

Pages (from-to) | 163-171 |

Number of pages | 9 |

Journal | Quaestiones Mathematicae |

Volume | 31 |

Issue number | 2 |

DOIs | |

Publication status | Published - Jun 2008 |

Externally published | Yes |

## Keywords

- Secure domination
- Vertex covers

## ASJC Scopus subject areas

- Mathematics (miscellaneous)