关键词: 定位控制集, 界, 容错定位控制集, 图论

Abstract: Given a graph G=(V, E), any nonempty subset S of V is called a locating-dominating set if the sets I(v)=N［v］∩S are nonempty and pairwise different for all v∈V-S, where N［v］ is the closed neighborhood of v. A locating-dominating set S is called a faulttolerant locating-dominating set of G if it can locate a faulty processor for any w∈V when all processors in S transmit the correct value 0, 1, or 2 and when exactly one device incorrectly transmits 0 rather than 1 or 2.This paper studies the fault-tolerant locating-dominating set. We present bounds of the minimum cardinality of the fault-tolerant locating-dominating set, both in finite graphs and in infinite triangular grids.

Key words: bound, fault-tolerant locating-dominating set, locating-dominating set, graph theory