罗马控制数、彩虹控制数及相关问题的研究

The domination theory of graph is a very important part of graph theory, and has been widely applied into interdisciplinary areas，such as computer science, the design and analysis of communication networks and the complexity of algorithms, etc. .Roman domination number comes from military strategy and rainbow domination number is introduced for resolving the Vizing Conjecture in the domination theory. In this project, we will mainly do the following work: (1) We will strengthen the condition of roman domination to meet the needs of network warfare; (2) As every roman dominating set is corresponding to a 2-rainbow dominating set of a graph, we will get some results about both of them and get some sharp bounds on radius, girth and connectivity, in order to support Vizing Conjecture; (3) The two domination problems are both NP-complete, so we will give linear algorithms or polonimal algorithms for some special graphs. The corresponding background of history and the value of applications have attracted lots of attentions from many famous experts.

图的控制理论是图论的重要组成部分，也是图论的难点之一，它被广泛应用于计算机科学、通讯网络的设计和分析、算法复杂性等诸多领域。.罗马控制数的研究来源于军事策略，要求每个没有军团驻扎的堡垒需要与一个驻扎两个军团的堡垒相邻，彩虹控制数的引进则是为了解决控制理论里的Vizing猜想。在本项目中，我们将做以下工作：(1)对于罗马控制数问题，为了满足网络战需求，我们将考虑没有军团驻扎的堡垒同时受到攻击的情形；(2)由于每个罗马控制集能对应到一个2-彩虹控制集，因此我们将这两个控制数结合起来考虑，在半径、围长和连通度等条件下，研究彩虹控制数的性质和上下界，并找到那些极图，为Vizing猜想的解决提供更多的理论基础和方法；(3)鉴于上述两个控制数问题都是NP-完备的，我们将给出一些特殊图类的线性算法或多项式近似算法。两个控制参数的历史背景和应用价值，已经吸引了国内外众多著名学者的关注。