期刊文献+

容错定位控制集的界

Bounds of Fault-Tolerant Locating-Dominating Sets
下载PDF
导出
摘要 给定图G=(V,E),S是V的任意一个非空子集,如果对所有的v∈V-S,集合I(v)=N[v]∩S都是非空且是两两不同的,那么称S是G的一个定位控制集.如果当S中所有的装置都传送正确的监测信息值0,1或2,或者仅有一个装置错误地传送数值0而不是1或2时,它都能测定出V中任何一个错误的处理器w,那么称S是G的一个容错定位控制集.研究了容错定位控制集,给出了容错定位控制集在几类有限图和无限三角形格子图中的一些界. 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.
机构地区 上海大学理学院
出处 《上海大学学报(自然科学版)》 CAS CSCD 北大核心 2008年第6期611-616,共6页 Journal of Shanghai University:Natural Science Edition
基金 国家自然科学基金资助项目(10571117 60773078 10832006) 上海市教育发展基金曙光计划资助项目(06SG42)
关键词 图论 定位控制集 容错定位控制集 graph theory locating-dominating set fault-tolerant locating-dominating set bound
  • 相关文献

参考文献13

  • 1SLATER P J. Dominating and reference sets in a graph [J]. J Math Phys Sci, 1998, 22:445-455.
  • 2SLATER P J. Domination and location in acyclicgraphs [J]. Networks, 1987, 17:55-64.
  • 3SLATER P J. Fault-tolerant locating-dominating sets [ J]. Discrete Math, 2002, 249:179-189.
  • 4HONKALA I, LAIHONEN T. On locating-dominating sets in infinite grids [ J ]. European J Combin, 2006, 27:218-227.
  • 5HONKALA I. An optimal locating-dominating set in the infinite triangular grid[J]. Discrete Math, 2006, 21 :2670-2681.
  • 6GIMBEL J, GORDEN B V, NICOLESCU M, et al. Location with dominating sets [ J]. Congr Numer, 2001, 151 : 129-144.
  • 7HAYNES T W, HENNING M A, HOWARD J. Locating and total dominating sets in trees [ J ]. Discrete Appl Math, 2006, 154:1293-1300.
  • 8KARPOVSKY M G, CHAKRABARTY K, LEVITIN L B. On a new class of codes for identifying vertices in graphs [J]. IEEE Trans Inform Theorey, 1998, 44(2) : 599-611.
  • 9BLASS U, HONKALA I, LITSYN S. Bounds on identifying codes [ J]. Discrete Math, 2001, 241: 119- 128.
  • 10GRAVIER S, MONCEL J. Construction of codes identifying sets of vertices [ J ]. Electron J Combin, 2005, 12(1) :R13.

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部