容错定位控制集的界

给定图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的一个容错定位控制集.研究了容错定位控制集,给出了容错定位控制集在几类有限图和无限三角形格子图中的一些界.

路和圈的3-LDS

图的控制集理论在图论领域中发展较快.尤其近几十年,图论研究不断深入,控制集理论方面的新参数不断涌现,在科学计算机、编码密码学、优化组合、网络通信、系统监视和网络社会等领域也有着重要的应用.在其基础上提出来的图的定位控制集就广泛应用于通讯网络和监视系统中,已经成为现在编码理论中较活跃的研究方向.即便对最简单的路和圈,找出一个图G的最小定位控制集是非常困难的.就路和圈的定位控制集问题,当r=1和2时的情形已给出结论.本文讨论当r=3时,定位控制集有关路和圈问题的完整结果.

路和圈的r-LDS的新上界

随着科技的发展,图论研究的不断深入,图的定位控制集也应运而生,成为图论迅速发展领域之一.图的控制集理论有着广泛重要的应用,在科学计算机、编码理论、优化组合、监控系统、社会网络和网络通信等领域都大显神通.有关图的定位控制集的新参数也不断涌现,已成为编码理论、优化组合中活跃的研究方向,在监控系统和网络通讯中受到重视.对于图G,即便是对最简单的路和圈,最小定位控制集的寻找确定十分困难.当r=1或2时,路和圈的定位控制集问题已解决.对于路和圈的最优定位控制集的下界Mr^LDG),已经由Bertrand等给出.本文对任意r≥2的情况,讨论得出路和圈的Mr^LD(G)的新上界.