Open-Locating-Dominating Sets

Abstract

For a graph G, distinguishing sets can be used for detection purposes. Whether it be setting up sensors to detect a thief in a facility or detecting a faulty component in a network of processors, these types of sets can be used to minimize the number of sensors required for the grid or network. Recently, there has been a lot of research into dealing with distinguishing sets, including on open-locating-dominating (OLD) sets, which is the graphical parameter this research focuses on.

A dominating set D is a subset of vertices in G where each of the vertices in G is either in D or adjacent to some vertex in D. An open-locating-dominating set is a special dominating set that is used to detect and pinpoint exact location of a problem vertex in a system. For a given graph G, OLD(G) denotes the minimum cardinality of an OLD set and the problem of determining the value of OLD(G) for an arbitrary graph G is known to be NP-complete.

For our research, programs were developed to find OLD sets and the value of OLD(G) for various classes of graphs. In particular, in order to find the minimum density of an OLD set for the infinite king's graph, an algorithm was created that parallelized the program using a backtracking algorithm and the program has confirmed the previous results. Most importantly we present a proof for the NP-completeness of a fault-tolerant OLD set called a redundant OLD set.