Liar's Domination in Grid Graphs

<p>As introduced by Slater in 2008, liar's domination provides a way of modeling protection devices where one may be faulty. Assume each vertex of a graph <em>G</em> is the possible location for an intruder such as a thief. A protection device at a vertex <em>v</em> is assumed to be able to detect the intruder at any vertex in its closed neighborhood N[<em>v</em>] and identify at which vertex in N[<em>v</em>] the intruder is located. A dominating set is required to identify any intruder's location in the graph <em>G</em>, and if any one device can fail to detect the intruder, then a double-dominating set is necessary. Stronger still, a liar's dominating set can identify an intruder's location even when any one device in the neighborhood of the intruder vertex can lie, that is, any one device in the neighborhood of the intruder vertex can misidentify any vertex in its closed neighborhood as the intruder location or fail to report an intruder in its closed neighborhood. In this thesis, we present the liar's domination number for the finite ladders, infinite ladder, and infinite P_3 x P_infty. We also give bounds for other grid graphs.</p>

Name thesis:degree_name

MS (Master of Science)

Level thesis:degree_level

Thesis - unrestricted

Discipline thesis:degree_discipline

Mathematical Sciences

Year dc:date.issued

2012

Author dc:creator

• Sterling, Christopher Kent

• graph theory
• liar's domination
• grid graphs
• ladders
• Discrete Mathematics and Combinatorics
• Mathematics
• Physical Sciences and Mathematics

Statement dc:rights

• Copyright by the authors.

Repository record dc:identifier

https://dc.etsu.edu/etd/1415

OAI identifier oai:identifier

oai:dc.etsu.edu:etd-2608