|
Protection of a Graph |
|---|
EJ Cockayne1, PJP Grobler2, WR Gründlingh2, J Munganga3 & JH van Vuuren2
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 previously studied 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.
An electronic version of the complete paper may be obtained here: [ps] [pdf].
Affiliations
1Department of Mathematics, University of Victoria, PO Box 1700 STN CSC, Victoria, BC V8W 2Y2, Canada,
email: cockayne@math.uvic.ca.
2Department of Applied Mathematics, Stellenbosch University, Private Bag X1, Matieland, 7602, Republic of South Africa, fax: +27 21 8083778, email: vuuren@sun.ac.za.
3Department of Mathematics, Applied Mathematics & Astronomy, University of South Africa, PO Box 392, Pretoria, 0003, South Africa.