论文部分内容阅读
图的控制理论是组合与图论的一个重要研究领域.三十多年来,随着图的控制理论不断发展和实际问题的需要,研究者提出了控制数的多种变形.本文主要围绕控制的Vizing猜想及控制理论中其他重要问题展开研究.主要研究对象有:{k}-控制、全控制和p-控制.
在第一章里,我们首先介绍图论的历史背景和一些常用的概念.然后,介绍经典控制的概念及其研究问题.
第二章重点讨论{k}-控制数.根据我们提出的划分和映射挪点新方法,得到了Cartesian乘积图的{k}-控制数的一个下界:γ{k}(G□H)≥ρ(G)γ{k}(H)+γ{m}(H),这里m=γ{k}(G)-kρ(G).这个下界包含并提高经典控制Vizing猜想的多个现有的结果,为解决Vizing猜想提供了一种新的方法.同时,我们提出的{k}-控制类Vizing猜想也能从这个下界得到部分证明.
第三章我们着重讨论全控制的一些等号刻画问题.3.2节分别刻画了所有满足等式2γt(K2□H)=γt(K2)γt(H)和2γt(Cn□H)=γt(CN)γt(H)的图H.3.3节刻画了所有(γt,2γ)-块图,从而将Henning的结果从树情形推广到块图情形.
第四章讨论树的p-控制.在4.2和4.3节,我们首先给出了树图p-控制数的一个下界,并刻画了达到这个下界的树;其次刻画了带有唯一最小p-控制集的树.在4.4节,我们提出新的概念—p-约束数bp(G),并证明了对于树T,1≤bp(T)≤△(T)-p+1,以及刻画了所有达到这些界的树.
最后,我们总结本文所做的结果,并提出一些值得进一步研究的问题.