Fault-tolerant locating-dominating sets Original Research Article

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