Fault-Tolerant Locating-Dominating Sets

Dr. Peter J. Slater

Department of Mathematical Sciences
University of Alabama in Huntsville

February 18, 2000

Abstract

For facilities safeguards problems in which one is interested in detecting the presence of, and determining the exact location of an intruder, and for determining an inoperable component in a processor network, locating-dominating sets are of interest. Vertex set S in graph G = (V, E) is a locating-dominating set if for each pair of distinct vertices u and v in V(G) − S, we have 

∅ ≠ N(u) ∩ S ≠ N(v) ∩S,

that is, each vertex outside of S is adjacent to a distinct, nonempty subset of the elements of S. The talk introduces the study of single-fault-tolerant locating-dominating sets. The percent of vertices in the 2-dimensional infinite grid required for a fault-tolerant locating-dominating set is between 52% and 60%, while that for just a locating-dominating set is 30%.