论文部分内容阅读
给定一个图G和一个集合DV(G),我们定义N_r[x]={x_i∈V(G):d(x,x_i)≤r},其中d(x,y)表示x和y在图G上的距离.令D_r(x)=N_r[x]∩D.若D满足:(1)对于图G的每一个点x,D_r(x)≠0;(2)对于任意两个不同的点x和y有D_r(x)≠D_r(y),那么称D为图G的一个r-验证码(简记为r-IC).D是图G的一个r-定位控制集(简记为r-LD),如果对于每一个点x∈V(G),D_r(x)≠0,并且对于任意两个不同的点x,y∈V(G)D,有D_r(x)≠D_r(y). 本文主要研究路和圈的r-IC以及圈的2-LD问题.Gravier et al.[Identifying codesof cycles,European Journal of Combinatorics 27(2006)767-776]对于圈和路的r-IC的最小值给出了部分结果;Roberts et al.[Locating sensors in paths and cycles:The caseof 2-identifying codes,European Journal of Combinatorics 29(2008)72-82]对于r=2的情形,给出了完整的结果.在这个基础上,本文对于任意的正整数r给出了圈和路的r-IC的最小值的全部结果,完善和推广了Gravier et al.和Roberts et al.的结果. 本文也给出了圈的2-LD的最小值的全部结果,这完善了Bertrand et al.[Identifyingand locating-dominating codes on chains and cycles,European Journal of Combinatorics 25(2004)969-987]的结果.