Vertex covers and secure domination in graphs
dc.contributor.author | Burger A.P. | |
dc.contributor.author | Henning M.A. | |
dc.contributor.author | Van Vuuren J.H. | |
dc.date.accessioned | 2011-05-15T16:05:22Z | |
dc.date.available | 2011-05-15T16:05:22Z | |
dc.date.issued | 2008 | |
dc.description.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 K2 or to an odd cycle. © 2008 NISC Pty Ltd. | |
dc.description.version | Article | |
dc.identifier.citation | Quaestiones Mathematicae | |
dc.identifier.citation | 31 | |
dc.identifier.citation | 2 | |
dc.identifier.issn | 16073606 | |
dc.identifier.other | 10.2989/QM.2008.31.2.5.477 | |
dc.identifier.uri | http://hdl.handle.net/10019.1/13100 | |
dc.title | Vertex covers and secure domination in graphs | |
dc.type | Article |