图的支配问题的研究

The fastest-growing area within graph theory is the study of domination and related problems. The project intends to study the domination number of graphs and the properties of domination critical graphs by using some existing tools in Combinatorics and Graph Theory and combining with the computer algorithm. Our research contains several aspects: the computation of the domanition number of generalized Petersen graphs, the characterization of the property of total domination critical graphs with prescribed conditions, and the research of the exact values or bounds for locating domination number of some special graphs. Among them, there are three open problems proposed in resent years. Through the exploration, we hope to solve these problems partially or completely and improve the best results, which will promote the development of the field.

图的支配理论是图论研究领域中近年来最为活跃的分支之一。本项目拟从图的支配数及其参数的静态和动态两个角度出发，利用组合数学和图论已有的研究工具并结合计算机算法的辅助，对图的支配数和支配临界图的性质进行研究。研究内容包括确定广义Petersen图的支配数；对满足一定条件的全支配临界图的性质进行刻画；对经典支配数的一类变形——位置支配数的确切值及上下界进行研究。其中包含近几年提出的三个公开问题。希望通过对此项目的探索，能部分或完全解决这几个公开问题，改进目前已有的最好结果，推进该学科的发展。

图的支配理论的研究是图论研究领域中近年来最为活跃的分支之一, 支配理论的发展还很不完善，待解决的课题以及公开的问题与猜想还有很多。本项目基于支配数理论自身的发展以及国内外研究动态，并紧密围绕项目计划书的预期研究内容进行了支配理论的三方面问题的研究。. 本项目在广义Petersen图P(n,k)的支配数方面对n=ck (c是任意正整数)时P(n,k)的支配数进行了研究，给出了其支配数的一个上界，该成果改进了W. Zhao、M. Zheng和L. Wu在2010年给出的P(ck,k)的支配数的上界，同时还确定了c=4,5,6时P(ck,k)的支配数；本项目在全支配临界图的性质刻画方面，解决了D.A. Mojdeh和N.J. Rad在2007年提出的两个公开问题；本项目在支配数的变形方面，解决了Atapour、Khodkar以及Sheikholeslam在2007年提出的关于双支配细分数研究的一个公开问题，此外还确定了广义Petersen 图P(n，2)的罗马支配数。本项目已经发表SCI 论文2篇，另外还有1篇论文被SCI杂志录用。