Research On Domination Number And Two Related Problems Of Graphs

Research on graph theory has not only extensive applications to both theoretic and applied problems, such as computer science, network theory, operations research, physics, chemistry and biology. Domination in graphs has become one of the major areas of graph theory with extensive applications in optimization theory, design and analysis of communication networks, computational complexity, and algorithm design. This thesis mainly research on domination number, Roman domination number, liar's domination number and distance paired domination number of generalized Petersen graphs and circulant graphs. In addition, other fields of graph theory such as domination critical properties and radio labeling have also been studied.Domination in graph originated from the problem concerning the minimum number of queen on a chessboard. The research on domination number of various graphs has always drawn wide attention. In this thesis, we studied the domination numbers of generalized Petersen graphs P(n, k), and gave an improved upper bound of P(n, k) for n=ck where c≥3 and k≥3. We also determined the exact values of the domination numbers of P(n, k) for the cases of c=4,5,6.Roman domination in graphs originated from military strategy of Roman Empire early in the 4th century BC. In this thesis, we studied the Roman domination numbers of generalized Petersen graphs P(n, k) and determined it for the case of k=2.Liar's domination in graphs was introduced by Slater in 2009. It has many important applications in fault detection of networks. In this thesis, we studied the liar's domination numbers of generalized Petersen graphs P(n, k) and determined it for the case of k=1,2.Distance paired domination in graphs was proposed by Joanna Raczek in 2008. Paired domination was introduced as a model for assigning backups to guards for security purposes, and distance domination stems from problems involving the placement of a minimum num-ber of facilities, both of which have extensive applications. In this thesis, we studied the k-distance paired domination numbers of generalized Petersen graphs P(n, k) and circulant graphs C(n;{l,k}). For any distance d, we gave the exact values of the d-distance paired domination numbers of generalized Petersen graphs P(n, k) for k=1,2 and circulant graphs C(n;{l,k}) for k=2,3,4.Domination critical problems is a branch of domination in graphs. Some properties of domination will vary with changes of the number of vertex in a graph. In 2006, Mojdeh et al. posed an open problem:Does there exist a 3-y,-critical graph G of orderΔ(G)+3 withΔ(G) odd? In this thesis, we constructed a family of 3-γ1-critical graphs with orderΔ(G)+3 and odd A(G)≥9, and proved that there did not exist 3-γ1-critical graph with orderΔ(G)+3 and odd A(G)=7, which solved this open problem.Radio labeling of graphs rooted in communication channel partition. In this thesis, we studied the radio labeling of cartesian product graphs P2□Pn and determined the radio number of it.The problems researched in this thesis are all NP-complete. Research on these problems are considered to provide a reference in solving general NP-hard problem, and the results enrich and develop the theory of domination and related theory of graphs.