On Domination Problem Of Graphs

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.