The Factor Of Domination Critical Graphs And Signed Domination In Graphs

Domination in graphs has become one of major reserach fields within graph theorey after more than thirty years' development. The importance of domination in graph theorey is attributable largely to two factors: (1) there is a close relation between domination in graphs and other science, such as combinatorial optimization, theoretical computer science and sociology. (2) domination theory has many and varied applications in practical problems, such as facility location, monitor system, communication networks. Now, the research on domination theorey focus on the following four aspects: (1) Studying the computational complexity of domination-related parameters and designing algorithm of domination-related parameters; (2) Determining the bounds on several domination parameters and characterizing the extremal graphs; (3) Studying the properties of domination critical graphs (4) Discussing applications of domination theory in other fields.In this dissertation, double domination edge critical graph, total domination vertex ctitical, clque-transversal number, signed total k-domination number and signed clque-transversal number are investigated.In Chapter 2, we investigate the properties of double domination edge critical graphs. Firstly, we show that double domination edge critical graphs with double domination number 3 have perfect matching. Further, we give some sufficient conditions such that double domination edge critical graphs are k-factor-critical. Finally, we provide some sufficient conditions such that double domination edge critical graphs with double domination number 4 have perfect matching or are factor-critical, bicritical and 3-factor-critical.In Chapter 3, we investigate the properties of total domination vertex critical graphs. We provide some sufficient conditions such that total domination vertex critical graphs with total domination number 3 or 4 have perfect matching or are factor-critical. In Chapter 4, Shan et. al. in [69] show that clique-transversal number of claw-free cubic graphs of order n is at most n/2. We give a complete characterization of claw-free cubic graphs with clique-transversal number n/2.In Chapter 5, we study the (upper) signed total k-domination number and signed clique-transversal number. Firstly, we determine the lower bounds on signed total k-domination number for general graphs, and characterize the extremal graphs attaining one of the lower bounds; Furthermore, we establish the lower bound on signed total k-domination number for K_r+1-free graphs, which generalize the result of bipartite graphs in [81]. Secondly, we show that the upper signed total k-domination problem is NP-complete for bipartite graphs, and give the upper bounds on upper signed total k-domination number for arbitrary graphs. Finally, we obtain the lower bounds on signed clique-transversal number for regular graphs with clique number at most 4, which improve the result in [86]. Furthermore, we also show that the signed clique-transversal problem is NP-complete for dually chordal graphs, and is solvable in polynomial time for strongly chordal graphs.