Degree Name
MS (Master of Science)
Program
Mathematical Sciences
Date of Award
5-2012
Committee Chair or Co-Chairs
Teresa W. Haynes
Committee Members
Anant P. Godbole, Debra J. Knisley
Abstract
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 G is the possible location for an intruder such as a thief. A protection device at a vertex v is assumed to be able to detect the intruder at any vertex in its closed neighborhood N[v] and identify at which vertex in N[v] the intruder is located. A dominating set is required to identify any intruder's location in the graph G, 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.
Document Type
Thesis - unrestricted
Recommended Citation
Sterling, Christopher Kent, "Liar's Domination in Grid Graphs" (2012). Electronic Theses and Dissertations. Paper 1415. https://dc.etsu.edu/etd/1415
Copyright
Copyright by the authors.