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. This paper 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%.
