图的控制约束问题研究

项目名称： 图的控制约束问题研究

项目编号： No.11401004

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 胡夫涛

作者单位： 安徽大学

项目金额： 22万元

中文摘要： 图的控制约束问题研究来源于图的控制理论，是度量图的控制脆弱性的参数。本项目将从国内外约束数研究的几个主要方面开展工作：(1) 确定约束数计算复杂性。许名著名网络都是二部图或者弦图，但是在二部图和弦图上计算约束数到底难度如何，是未知的。本项目将深入研究约束数在某些特殊图类(如：二部图和弦图)上对应的判定问题的计算复杂性，为进一步研究该参数的界、近似算法等相关问题提供理论基础；(2) 用其它图论参数给出约束数较好的界，解决平面图约束数猜想在最大度位于3和6之间的剩余情形，将约束数较好的界(如在点可迁图上的结果)推广到全约束数等变形上；(3) 给出某些经典网络（如：星网络、煎饼网络和(环面)网格网络等）约束数精确值或者界，为人们在实际中使用这些网络时提供一定的参考。此外，本项目还将考虑其它变形约束数对应的相关问题。本项目的研究将对图控制理论研究和发展起一定推动作用。

中文关键词： 控制数；约束数；复杂性；互联网络；控制划分数

英文摘要： The researches of bondage number in graphs come from the domination theory, which is a parameter that measures the vulnerability of domination. This project will mainly do some works depending on several key aspects of the home and abroad researches of bo

英文关键词： Domination Number；Bondage Number；Complexity；Internet Networks；Domatic number