图的p-控制理论与算法研究

The p-domination number is a natural extension of the classic domination number. As a tool, p-domination number is more and more widely applied in interconnection networks. However, the study of the problems raised in the applications is still lacking. To improve this situation, this project will focus on the following contents: the p-domination number of product graphs, the stability of p-domination, and the algorithms for minimum p-dominating sets.. For the p-domination number of product graphs, we will apply a new method to establish its lower bounds in terms of the p-domination numbers of the two factor graphs, and these lower bounds may contribute to improve the existed results of Vizing's conjecture. For the stability of p-domination, we plan to study the p-bondage and p-reinforcement numbers of graphs and establish their upper bounds by introducing some equivalent parameters. We also consider the relationships between two p-bondage (p-reinforcement) numbers. For the problem on finding the minimum p-dominating sets in a graph, we first transform it into another problem of expanding a logical expression, which is defined in the vertex-set of the graph, and then use the knowledge of graph theory, algebra and computer science to design and prove the algorithms for finding minimum p-dominating sets in the graph. Moreover, we will further explore how to apply this transformation to more p-domination problems. . The project is expected to not only solve several key problems in the above contents and obtain a breakthrough in the thoughts and methods of p-domination problems, but also contribute to enrich and expand domination theory of graph.

图的p-控制数是控制数的自然推广，以它为工具在互连网络中应用日益广泛，但对应用过程中提出的问题，现有研究明显不足。针对其中突出问题，本项目着重研究下列内容：乘积图的p-控制数、p-控制的稳定性和最小p-控制集算法。. 对乘积图的p-控制数，拟引入新的分块挪点法建立用因子图的p-控制数表示的下界，以期促进Vizing猜想的研究。对p-控制的稳定性，主要研究p-约束数和p-加强数，以构造相等参数的方法在一般图上给出它们的取值范围，同时还将探讨不同p取值的p-约束数(p-加强数)相互关系。对于设计算法求最小p-控制集问题，先通过定义顶点集上逻辑运算将该问题转化为逻辑表达式的展开问题，再综合运用图论、代数和计算机等手段，设计并证明最小p-控制集算法，并进一步探讨该转化在更多p-控制问题中应用。. 本项目预计解决上述内容中一些关键问题，并在研究思路和方法上取得突破，丰富发展图的控制理论。

图的p-控制数是图的控制理论的一个重要研究课题, 是经典控制数的一个自然推广. 面对其在互连网络中应用出现的各种问题, 本项目着重研究下面内容. 首先, 由于确定一般图的p-控制数问题是NP-完全的, 所以本项目在包括Cartesian乘积图、完全多部图等特殊图类上研究其p-控制数的取值范围或者精确表达式具有重要的理论意义. 结合最小p-控制集的结构特点, 我们获得了完全多部图p-控制数的精确表达式, 以及其他图类上p-控制集的一些关键性质, 为进一步研究提供重要基础. 其次, 根据给图加边其p-控制数可能减少这一性质, 引入图的p-加强数来研究p-控制数的稳定性. 本项目建立了一般图上p-加强数的等价公式, 并利用这个等价公式, 证明了对于每个固定的p, 确定一般图的p-加强数是一个NP-困难问题; 确定了路、圈、完全多部图等特殊图类上p-加强数的精确表达式; 建立了p-加强数的一些上界同时完全刻画了达到这些上界的极值树图. 最后, 研究图的着色问题. 在无向图上, 对邻集可区分与邻和可区分两个全着色猜想展开研究, 证明了邻集可区分全着色猜想在所有最大度为4的图上都是正确的, 还在更强的列表情形下, 建立了邻和可区分全着色数新的上界以及证明了邻和可区分全着色猜想对于所有2-退化图都是正确的. 在有向图上, 研究有向图的弧着色, 因为给有向图的所有弧着色需要最少的颜色数等于覆盖所有边需最少的定向割数, 所以借助Alon等人关于定向割覆盖的经典结论, 我们在出度至多是k (k=5,6,7)或入度至多是k这一大图类上建立了弧着色数范围, 同时也给出了一般有向图弧着色数的一个下界.