Identifying codes and locating-dominating sets on paths and cycles
Identifying codes and locating-dominating sets on paths and cycles
复制标题
识别代码并定位路径和循环上的主导集
DOI：
10.1016/j.dam.2011.06.008
复制
发表时间：
2009-08
影响因子：
1.1
通讯作者：
Miao, Zhengke
中科院分区：
文献类型：
--
作者：
Chen, Chunxia;Lu, Changhong;Miao, Zhengke
设 G=(V,E) 为图，r≥1 为整数。对于集合 D⊆V，定义 Nr[x]={y∈V:d(x,y)≤r} 和 Dr(x)=Nr[x]∩D，其中 d(x,y) 表示 x 和 y 之间任何最短路径中的边数。 D 被称为 r 识别码（分别为 r 定位支配集），如果对于所有顶点 x ∈ V （分别为 x ∈ V ∖D ），Dr(x) 都是非空且不同的。罗伯茨和罗伯茨 [D.L.罗伯茨，F.S. Roberts，在路径和循环中定位传感器：2 识别码的情况，欧洲组合学杂志 29 (2008) 72–82] 提供了 r=2 时路径和循环的完整结果。在本文中，我们提供了循环中剩余未决案例的结果以及 r 识别代码的路径中的完整结果；我们还给出了循环中 2 定位支配集的完整结果，这完善了 Bertrand 等人的结果。 [N. Bertrand, I. Charon, O. Hudry, A. Lobstein，识别和定位链和循环上的主导代码，欧洲组合学杂志 25 (2004) 969–987]。
Let G=(V,E) be a graph and let r≥1 be an integer. For a set D⊆V, define Nr[x]={y∈V:d(x,y)≤r} and Dr(x)=Nr[x]∩D, where d(x,y) denotes the number of edges in any shortest path between x and y. D is known as an r-identifying code (r-locating-dominating set, respectively), if for all vertices x∈V (x∈V∖D, respectively), Dr(x) are all nonempty and different. Roberts and Roberts [D.L. Roberts, F.S. Roberts, Locating sensors in paths and cycles: the case of 2-identifying codes, European Journal of Combinatorics 29 (2008) 72–82] provided complete results for the paths and cycles when r=2. In this paper, we provide results for a remaining open case in cycles and complete results in paths for r-identifying codes; we also give complete results for 2-locating-dominating sets in cycles, which completes the results of 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].
登录
查看更多内容
DOI：
10.1016/s0304-3975(02)00536-4
发表时间：
2003-01
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
I. Charon;O. Hudry;A. Lobstein
通讯作者：
I. Charon;O. Hudry;A. Lobstein
DOI：
10.1016/j.ejc.2008.04.011
发表时间：
2009-05
期刊：
Eur. J. Comb.
影响因子：
--
作者：
通讯作者：
--
DOI：
10.1016/s0012-365x(01)00113-3
发表时间：
2001-10
期刊：
Discret. Math.
影响因子：
--
作者：
U. Blass;I. Honkala;S. Litsyn
通讯作者：
U. Blass;I. Honkala;S. Litsyn
DOI：
10.1109/18.661507
发表时间：
1998-03
期刊：
IEEE Trans. Inf. Theory
影响因子：
--
作者：
M. Karpovsky;K. Chakrabarty;L. Levitin
通讯作者：
M. Karpovsky;K. Chakrabarty;L. Levitin
DOI：
10.37236/1451
发表时间：
1999-03
期刊：
Electron. J. Comb.
影响因子：
--
作者：
G. Cohen;I. Honkala;A. Lobstein;G. Zémor
通讯作者：
G. Cohen;I. Honkala;A. Lobstein;G. Zémor