Study On Paired-Domination Problem In Graphs With Mechanization

Let G= (V, E) be a simple undirected graph without isolated vertices. A set S C V is a dominating set of G if every vertex in V - S is adjacent to at least one vertex in S. A set S C V is a paired-dominating set of G if 5 is a dominating set of G and the induced subgraph G[S] has a perfect matching. The paired-domination number of G, denoted byγpr(G), is defined as min{|S|| S is a paired-dominating set of G}. The paired-domination problem is to determine the paired-domination number. The paired-domination problem was first proposed by T. W. Haynes and P. J. Slater, and they prove that it is NP-complete for general graphs. In this paper, we continue the research of paired-domination problem and related problems. The main results are as follows:Part I, give the analysis of hardness and approximation hardness on paired-domination problem. T. W. Haynes and P. J. Slater have proved that paired-domination problem is NP-complete for general graphs. We prove that it is still NP-complete for bipartite graphs and split graphs. In the research of approximation algorithms on paired-domination problem, we give the upper and lower bounds on approximation ratio. Furthermore, the paired-domination problem is APX-complete for graphs with maximum degree at most 3.Part II, give the polynomial time algorithms for paired-domination problem in inter-val graphs, trees, block graphs and strongly chordal graphs using labelling method, and we prove the correctness of these algorithms. Algorithm MPDS for paired-domination problem in strongly chordal graphs is the biggest contribution in this paper, which gener-alizes many algorithms proposed by other researchers. Furthermore, the algorithm MPBS is implemented in Maple.Part III, give the analysis of block graphs and vertices in block graphs with the special properties of the minimum paired-dominating set. There are two main results. First, give a characterization for block graphs with unique minimum paired-dominating set, which extends the former result for trees. Second, give a method to filter vertices in block graphs which are contained in all minimum paired-dominating sets. It also extends the former result for trees.Part IV, give some results on k-distance paired-domination problem and weighted paired-domination problem. We give some polynomial time algorithms for k-distance paired-domination problem in interval graphs and block graphs using labelling method, and prove the correctness of these algorithms. In addition, an approximation algorithm in general graphs and an efficient algorithm in trees for weighted paired-domination problem are given.