摘要
给定图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