This thesis introduces a new strategy of defending the vertices of a graph - secure
paired domination, where guards are required to be paired and, when a vertex is
attacked, one or two guards move to defend the attacked vertex, while keeping the
graph dominated and the guards paired after the move. We propose nine possible
definitions of secure paired domination, compare and contrast each with the others,
and obtain properties and inequalities of the secure paired domination (SPD) numbers associated with the definitions. Based on each of the nine definitions, the SPD numbers of five types of special graphs, namely paths, cycles, spiders, ladders and grid graphs, are studied.
We then compare the SPD number of an arbitrary isolate-free graph to various
other parameters such as clique partition number, independence number, vertex-
covering number, secure domination number and paired domination number. We
establish that, for any graph without isolated vertices, its SPD number does not
exceed twice the value of any of its other parameters mentioned above. Also, we give classes of trees for which some of the bounds are achieved. As conclusion, some open problems and directions for further studies regarding secure paired domination are listed.
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/3015 |
| Date | 31 August 2010 |
| Creators | Kang, Jian |
| Contributors | Mynhardt, C. M. |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web |
Page generated in 0.0026 seconds