论文部分内容阅读
图的控制理论是图论中的一个重要研究领域.自从上个世纪八十年代以来,控制理论根据不同的实际应用背景,演化出各种不同性质的的控制数.这篇论文主要研究其中两种重要的控制:全{k}-控制和符号控制.在第一部分中,我们首先介绍图论的发展历史背景及一些常用的术语概念.然后,再给出比较经典的控制数的概念其研究问题.第二部分中,我们主要探讨全{k}-控制数以及笛卡尔乘积图的全{k}-控制数的一个下界:γt{k}（G）γt{k}（G）≤k（k+1）γt{k}（G□H）.这个结果包含并提高了全控制数及全{k}-控制数的Vizing猜想的多个已有结果.并且彻底解决了Henning和Rall 2005年在[On the total domination number of Cartesian product of graph,Graphs and combinatorics 21（2005）,63-69 ]一文中提出的关于笛卡尔乘积图的全控制数的一个猜想γ{t}（G）γ{t}（G）≤2γ{t}（G□H）.从而解决了全控制数的Vizing-like问题.然后我们研究了全{k}-控制划分数问题,特别是得到了完全图的全{k}-控制划分数的上界.从而解决了S.M. Sheikholeslami和L. Volkmann在[The total k?domatic number of a graph, Journal of Combinatorial Optimization]一文中提出的完全图的全k?控制划分数问题.第三部分中,我们主要是研究了符号控制数的稳定性问题:符号控制数的约束数和符号控制数的加强数.我们首先给出了常见几类图的符号加强数和符号约束数.然后我们给出了树图的符号控制数的上界: Rs（T）≤2,并且证明了此上界的紧性,给出了上界取等号时的几类图.