图控制理论中Vizing猜想研究

Domination theory is an important and classic conception who have a wide range of applications in physical and computer discipline. The Cartesian product method is such a very effective method for constructing a lager graph from several small graph that it is an important method for designing large-scale interconnection networks. Vizing proposed the famous Vizing conjecture about the domination number of the Cartesian product graphs in 1963, this conjecture in graph domination theory remains open to this day. This project will mainly do some works depending on several key aspects of the home and abroad researches of Vizing conjecture:(1)Study specific families of graphs containing almost all the graphs that satisfy Vizing conjecture.(2)Discuss the inequality $\gamma(G\BoxH)\gec\gamma(G)\gamma(H)$ with deferent value of c, where $c\in(\frac{1}{2},1)$.(3)Research the Vizing-like inequality on the variant domination number, namely, study the relation between the variant domination number of the Cartesian product graphs and the product of the variant domination numbers of factors. The progress and the settlement of all those questions can enrich the development of the graph domination theory and better motivate the research on the related problem of Vizing conjecture.

控制理论是图论中重要且经典的概念，其在物理、计算机等许多学科有广泛的应用。笛卡尔乘积是图论中利用小图构造大图的一个有效方法，是设计大型互联网络的重要方法。Vizing在1963年提出了有关笛卡尔乘积图控制数的著名Vizing猜想，至今还未被解决。本项目将从国内外Vizing猜想研究的几个主要方面开展工作:(1)研究满足Vizing猜想的包含几乎所有图的特殊图类;(2)探讨常数c不同取值时的不等式$\gamma(G\BoxH)\ge c \gamma(G)\gamma(H)$，其中$c\in(\frac{1}{2},1)$;(3)研究变形控制数环境下的类Vizing不等式，即考虑笛卡尔乘积图变形控制数与因子图变形控制数乘积间的关系。这些问题的解决可以丰富图的控制理论的发展，推动Vizing猜想问题的进一步研究。

图控制理论中的Vizing猜想自1963年提出以来备受关注。虽然由于本身固有的难度导致Vizing猜想至今还未被解决，但是衍生出了与控制数相关图参数的类Vizing不等式的丰富研究成果。本项目着重于控制数、变形控制数及特殊图类Vizing猜想的相关研究，得到如下一些结论：(1)利用图的平均离心率刻画了控制数紧的界，并且改进了树的上述结果，得到了更优化的上界结论。另外，分别利用临近度和偏离度确定了控制数紧的上界。(2)研究变形控制数中的距离k-控制数与离心距离和的关系，构造了给定距离k控制数时取值最小离心距离和的树。(3)对于n≡0,3,4(mod5)，得到了广义Petersen图P(n,2)的精确值；对于n≡1,2(mod5)，得到了广义Petersen图P(n,2)的界。本项目的研究成果有望实现控制数及距离k-控制数的Vizing猜想转换为简单的距离相关图参数的类Vizing不等式进行研究，并且为Petersen图约束数的类Vizing不等式研究提供了理论基础。已发表与基金相关且挂有基金号的学术论文6篇，其中SCI检索5篇。