【作者】 李宁；

【导师】 徐俊明； 侯新民；

【作者基本信息】 中国科学技术大学 ， 应用数学， 2011， 博士

【摘要】 图的控制理论是图论中的一个重要研究领域.自从上个世纪八十年代以来,控制理论根据不同的实际应用背景,演化出各种不同性质的的控制数.这篇论文主要研究其中两种重要的控制:全{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?控制划分数问题.第三部分中,我们主要是研究了符号控制数的稳定性问题:符号控制数的约束数和符号控制数的加强数.我们首先给出了常见几类图的符号加强数和符号约束数.然后我们给出了树图的符号控制数的上界: R_s（T）≤2,并且证明了此上界的紧性,给出了上界取等号时的几类图.更多还原

【Abstract】 The study of dominations has become to be one of the best important top-ics in combinatorics and graph theory. Since the eighty of the last century, theconcepts of various dominations with special properties according to the di?erenceof practical backgrounds have been proposed from the classic domination. Thisthesis mainly study two kinds of important dominations, the total {k}-dominationand the reinforcement number of the signed domination number.In Part 1, besides introducing the developing background and some conceptsof graph theory, we mainly present the de?nition of domination numbers andresearch problems on domination theory.In Part 2, we mainly discuss the total {k}-domination. At the beginning,we get the lower bound of the total {k}-domination number of Cartesian productgraphs, that is,γt^{k}（G）γt^{k}（G）≤k（k+1）γt^{k}（G□H）. This lower bound containsand improves some known results on Vizing’s conjectures on the total dominationnumber and the total {k}-domination number, and so we give a proof for theconjecture proposed by Henning and Rall in [ On the total domination number ofCartesian product of graphs, Graphs and Combinatorics]. So we solve the Vizing-like problem on the total domination number. Then, we study the total k-domaticnumber of a graph. We obtain an upper bound of the total k-domatic numberof a complete graph, and then give an answer to the question proposed by S. M.Sheikholeslami and L. Volkmann in the forthcoming paper [The total k-domaticnumber of a graph, Journal of Combinatorial Optimization].In Part 3, we introduce the concepts of the bondage number and the reinforce-ment number of the signed domination number, and determine the reinforcementnumber of the signed domination number of some normal graphs. Especially, weget the upper bound of the reinforcement number R_s of the signed dominationnumber of a tree T, that is, R_s（T）≤2. In fact, we prove that the bound is tight and give graphs achieving the upper bound.In the end, we survey our main research results in this thesis, and provide someimmature results on the reinforcement number of the signed domination number.We also propose some questions that are worthy of further deep consideration.更多还原