Protection of a Graph

Abstract

For vertex v of a simple n-vertex graph G = (V, E) let f (v) be the number of guards stationed at v. A guard at v can deal with a problem at any vertex in its closed neighbourhood. We consider four strategies, i. e. properties of such functions under which the entire graph may be deemed protected. The four properties are domination, Roman domination, weak Roman domination which have been studied previously and a new concept called secure domination. The four parameters which give the minimum number of guards required to protect the graph under the various strategies, are studied. Exact values or bounds are obtained for specific classes of graphs. We also give a characterisation of those secure dominating sets which are minimal.