For a graph G and a set DV(G), define Nr[x]={xiV(G):d(x,xi)≤r} (where d(x,y) is graph theoretic distance) and Dr(x)=Nr[x]∩D. D is known as an r-identifying code if for every vertex x,Dr(x)≠0/, and for every pair of vertices x and y, x≠yDr(x)≠Dr(y). The various applications of these codes include attack sensor placement in networks and fault detection/localization in multiprocessor or distributed systems. Bertrand et al. [N. Bertrand, I. Charon, O. Hudry, A. Lobstein, Identifying and locating–dominating codes on chains and cycles, European Journal of Combinatorics 25 (2004) 969–987] and Gravier et al. [S. Gravier, J. Moncel, A. Semri, Identifying codes of cycles, European Journal of Combinatorics 27 (2006) 767–776] provide partial results about the minimum size of D for r-identifying codes for paths and cycles and present complete closed form solutions for the case r=1, based in part on Daniel [M. Daniel, Codes identifiants, Rapport pour le DEA ROCO, Grenoble, June 2003]. We provide complete solutions for the case r=2.
展开▼
机译：对于图G和集合DV（G），定义Nr [x] = {xiV（G）：d（x，xi）≤r}（其中d（x，y）是图理论距离）和Dr（x ）= Nr [x]∩D。如果对于每个顶点x，Dr（x）≠0 /，并且对于每对顶点x和y，x≠yDr（x）≠Dr（y），D被称为r识别码。这些代码的各种应用包括在网络中放置攻击传感器以及在多处理器或分布式系统中进行故障检测/定位。 Bertrand等。 [N. Bertrand，I。Charon，O。Hudry，A。Lobstein，《识别和定位链和循环上的主导代码》，《欧洲组合杂志》 25（2004）969–987]和Gravier等。 [S. Gravier，J. Moncel，A. Semri，“识别循环代码”，《欧洲组合杂志》 27（2006）767–776]提供了关于D的最小尺寸的部分结果，用于r识别路径和循环的代码，并给出了完全封闭的形式r = 1时的解决方案，部分基于Daniel [M.丹尼尔（Daniel），代码识别者，Rapport pour le DEA ROCO，格勒诺布尔，2003年6月]。对于r = 2的情况，我们提供完整的解决方案。
展开▼
