


























A locating-dominating set is a subset of vertices representing "detectors" in a graph G; each detector monitors its closed neighborhood and can distinguish its own location from its neighbors, and given all sensor input, the system can locate an "intruder" anywhere in the graph. We explore a fault-tolerant variant of locating-dominating sets, error-correcting locating-dominating (ERR:LD) sets, which can tolerate an incorrect signal from a single detector. In particular, we characterize error-correcting locating-dominating sets, and derive its existence criteria. We also prove that the problem of determining the minimum cardinality of ERR:LD set in arbitrary graphs 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 the lower bound for cubic graphs is sharp.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。