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 - Open Access

Copyright

Copyright by the authors.

Share

COinS