| After several decades’development, domination theory has increasingly be-come an active researching area in graph theory. Various domination-related pa-rameters have been put forward due to different practical backgrounds. The rapid development of domination theory is mainly based on the following facts:First, there are close relationships between domination problems and problems from other fields, such as combinatorial optimization, theoretical computer science and sociol-ogy; Secondly, domination theory has direct applications in many practical prob-lems, for example, in facility location, monitor system, communication networks, and so on. The researches on domination-related parameters mainly focus on the following aspects:effective algorithms and complexity, bounds, characterization of the extremal graphs, exact values for some special graph classes, etc.In the present dissertation, domination, signed domination, minus domination, signed total domination, minus total domination, paired domination, mixed dom-ination, signed mixed domination,K-distance domination, and K-step domination are investigated. We mainly focus on the the aspects of computational complexities and exact values of these parameters. The main works are stated as follows.In Chapter 2, we mainly investigate some common domination-related pa-rameters including signed domination, minus domination, signed total domination, minus total domination, and paired domination. We compute the exact values of these parameters for some classes of special graphs, and provide in the last section of the chapter an NP-completeness result of the domination problem.In Chapter 3, a comprehensive research is done to the computability of mixed domination problem. We provide two polynomial algorithms for determining the mixed domination numbers of trees, and show that mixed domination problem is NP-complete even when instances are restricted to split graphs. In Chapter 4, we study signed mixed domination problem. Lv [76] has in-troduced this concept and computed the values of the signed mixed domination numbers of paths and cycles. We prove that this problem is NP-complete for pla-nar graphs, and provide the exact values of the signed mixed domination numbers of complete graphs and complete bipartite graphs.In Chapter 5, we pay attention to distance domination and step domination problems. A linear-time algorithm for finding the 2-step domination number of a tree is first designed. Then, a new algorithm for determining the K-distance domination number of a tree is obtained similarly. |
