Fault-tolerant locating-dominating sets with error-correction

Source abstract

A locating-dominating set is a subset of vertices representing “detectors” placed within a graph for the purpose of identifying the location of some unwanted anomaly known as an “intruder.” Specifically, each detector in a locating-dominating set is able to monitor its closed neighborhood and can distinguish its own location from its neighbors. We explore a fault-tolerant variant of locating-dominating sets called error-correcting locating-dominating (ERR:LD) sets, which can tolerate at most one incorrect reading from a detector. In particular, we fully characterize ERR:LD sets for an arbitrary graph and derive their existence criteria. We also prove that the problem of determining the minimum cardinality of an ERR:LD set in an arbitrary graph is NP-complete. Additionally, we establish lower and upper bounds for the minimum density of ERR:LD sets in infinite grids and cubic graphs, and prove this lower bound for cubic graphs is sharp.