约束数及相关问题研究

约束（bondage）数是度量控制数的脆弱性（即图的边发生故障对控制数的影响）参数。约束数的概念自上世纪九十年代提出以来，存在大量的研究问题和猜想，至今还没有解决。本项目围绕约束数的研究热点问题，弄清约束数（包括各种限制条件下的约束数）计算复杂性；围绕 Dunbar 等人和 Fischermann 等人关于平面图约束数不超过最大度加1或者不超过7的猜想，研究控制临界图的结构性质；围绕 Teschner 关于任何图的约束数不超过它的最大度的1.5倍的猜想，利用其它图论参数，给出约束数的新的紧的上界和下界，确定某些有很强应用背景的特殊图的约束数。研究各种限制条件下的约束数，如限制约束数、全约束数、连通约束数、成对约束数等。解决这些问题的关键是进一步研究图的结构性质，寻找约束数与其它图论参数之间的关系，使用的方法主要是图论分析方法，附之以概率方法和计算机模拟。

本项目研究图的约束数及其相关问题。约束（bondage）和加强数(reinforcement)数是度量控制数的脆弱性（即图的边减少或者添加对控制数的影响）参数,在网络分析中有重要应用。本项目弄清了约束数和加强数的计算复杂性；证明了对于任意的图，确定其约束数、全约束数、加强数和全加强数问题都是NP-hard问题，而且不是NP完备的除非NP=P。围绕 Dunbar 等人和 Fischermann 等人关于平面图约束数的猜想，证明了利用约束数的现有结论是不可能解决这些猜想的。本项目研究各种限制条件下的控制与约束数，如p控制、符号控制、Roman控制及约束数等,对于某些特殊的图类，确定了相关参数的值。本项目共完成学术论文17 篇, 其中发表16 篇, 接收1 篇。这些研究成果大大丰富和完善了图的控制理论,也为分析网络性能提供进一步的理论基础。