On Domination Theory Of Graphs

The domination theory of graphs is an important topic in combination and graph theory. In the last thirty years, the classic domination have derived various other domi-nations according to the difference of practical problems. This thesis mainly study three kinds of important dominations:{k}-domination,total domination and p-domination..In Chapter 1, besides introducing the background and some concepts of graph theory, we mainly present the definition of domination and research problems on dom-ination theory.In Chapter 2, we mainly discuss{k}-domination. By applying new method, we give a lower bound of the{k}-domination number of Cartesian product graphs, that is,γ{k}(G□H)≥ρ(G)γ{k}{H)+γ{m}(H), where m=γ{k}(G)-kp(G). This lower bound contains some known results on Vizing's conjecture, and so we provide a general and concise proof for these results. In addition, we post the{k}-domination version of Vizing's conjecture, and partially prove that it is true by this lower bound.In Chapter 3, we give some characterizations on total domination. Section 3.2 characterize all graphs H satisfying 2γt(K2□H)=γt(K2)γt(H) and 2γt(Cn□H)=γt{Cn)γt(H), respectively. Section 3.3 give a characterization of (γt,2γ)-block graphs, which generalizes the result given by Henning.In Chapter 4, we study some problems on p-domination. In Sections 4.2 and 4.3, we first give a lower bound of p-domination number of trees and characterize all trees attaining this lower bound; and then we give a characterization of trees with unique minimum p-dominating set. In Section 4.4, we introduce a new concept-p-bondage number bp(G), show that 1≤bp(T)≤Δ(T)-p+1 for any tree T, and characterize all trees achieving the equalities.In the end, we conclude our results in this paper, and provide some problems that are worthy of further consideration.