| 容错定位控制集的界 |
| |
| 引用本文： | 李明松,单而芳,高明晶.容错定位控制集的界[J].上海大学学报(自然科学版),2008,14(6):611-616. |
| |
| 作者姓名： | 李明松 单而芳 高明晶 |
| |
| 作者单位： | (上海大学 理学院,上海 200444) |
| |
| 基金项目： | 国家自然科学基金
，
上海市"曙光计划"
|
| |
| 摘 要： | 给定图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的一个容错定位控制集.研究了容错定位控制集,给出了容错定位控制集在几类有限图和无限三角形格子图中的一些界.
|
| 关 键 词： | 定位控制集 界 容错定位控制集 图论 |
| 收稿时间： | 2007-10-23 |
Bounds of Fault-Tolerant Locating-Dominating Sets |
| |
| LI Ming-song,SHAN Er-fang,GAO Ming-jing.Bounds of Fault-Tolerant Locating-Dominating Sets[J].Journal of Shanghai University(Natural Science),2008,14(6):611-616. |
| |
| Authors: | LI Ming-song SHAN Er-fang GAO Ming-jing |
| |
| Affiliation: | (College of Sciences, Shanghai University, Shanghai 200444, China) |
| |
| Abstract: | 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. |
| |
| Keywords: | bound fault-tolerant locating-dominating set locating-dominating set graph theory |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《上海大学学报(自然科学版)》浏览原始摘要信息 |
|
点击此处可从《上海大学学报(自然科学版)》下载全文 |
|
