A linear algorithm for secure domination in trees

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. The secure domination number of G, denoted by γs(G...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2014-07, Vol.171, p.15-27
Main Authors: Burger, A.P., de Villiers, A.P., van Vuuren, J.H.
Format: Article
Language:English
Subjects:
(Wounded) spider
Algorithms
Graph protection
Graphs
Linear algorithm
Mathematical analysis
Neighbouring
Pruning
Secure domination
Spiders
Strategy
Tree
Trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. The secure domination number of G, denoted by γs(G), is the cardinality of a smallest secure dominating set of G. A linear algorithm is proposed in this paper for finding a minimum secure dominating set and hence the value γs(T) for a tree T. The algorithm is based on a strategy of repeatedly pruning away pendent spiders of T after having dominated them securely.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2014.02.001