路和圈的r-LDS的新上界

Paths and cycles have new upper bound about r-LDS

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

Domination problem has a wide range of important applications in coding theory,combinatorial optimization,computer science,surveillance systems,communication networks and social networks.It has become one of the fastest growing fields in graph theory in recent decades.With the deepening of research,the new control parameters continue to emerge,and the locating-dominating set of the graph has emerged as well.The locating-dominating set of the graph has become an more active research direction in coding theory,and it is widely used in monitoring systems and communication networks.Figure G,even for the simplest paths and circles,it is pretty difficult to find the minimum locating-dominating set.When r=1 or r=2,the problem of the locating-dominating set of the path and the circle has been solved.For the path and circle Mr^LD(G),Its lower bound has been given by Bertrand et al.In this paper,for the case of randomr≥2,the new upper bound of the Mr^LD(G)of the path and the circle is discussed and obtained results.