Study On Dominating Sets In Graphs And Related Problems

Dominating set is an important concept in graph theory, which is defined as an a vertexsubset such that every other vertex not in it must be adjacent to some vertex in this subset.The definition of dominating set was first introduced by Konig, Berge and Ore, theirbooks and some of papers by Cockayne, Hedetniemi, Larskar and Walikar motivated interestof later researchers.In the past thirty years, research on different kinds of domination parameters and theirrelation with other graph parameters become an active research field in graph theory. Duringthis phase, new domination related parameters are introduced continuously, such as con-nected dominating set and distance dominating set, etc. In this thesis, we introduce a newparameter—"[r,R]-dominating set", and analyze its algorithmic qualities.How to find a minimum dominating set is NP-hard, which can not be solved efficientlyvia backtracking or randomized algorithms, in this case, we try to find approximation al-gorithms instead. An approximation algorithms can be run in polynomial time and get areasonably good solution to given problems. To a minimizing problem, the performanceration of an approximation algorithms is defined as the ration of returned solution of our al-gorithm to the optimal solution in theory. Unfortunately, not all the problems can be solvedvia approximation algorithms with constant performance ratio, for example, under the as-sumption of P = NP, there does not exist an approximation algorithm for the problem ofminimum dominating set with performance ratio smaller than O(ln n).In Chapter 2 of this thesis, we present an algorithm for the minimum [r,R]-dominatingset problem with performance ratio lnΔ_r + [(2r+1)/R]-1. In general graphs, this result can't bebettered too much. After that, we consider the relation between the cardinalities of an [r,R]-dominating set and the given graph, the relation between [r,R]-dominating sets of a graphand its complement, and the relation between [r,R]-dominating set and total dominating set,then to give three types of upper bounds for a [r,R]-dominating set. In Chapter 3, we restrict the minimum [r,R]-dominating set in Unit Disk Graphs forpractical reasons, based on the special geometry structure, we get an algorithm with con-stant performance ratio [4r(r + 1)(1 - (2θ-sin(2θ)/π)][(r+1)/R], whereθ= arccos(R/(2+1)), for exactparameters, this can be improved.In Chapter 4 of this thesis, we restrict the minimum [r,R]-dominating set in randomregular graphs, by taking advantage of maximal independent sets we list a randomized algo-rithm, and analyze its performance with differential equations. Moreover, we get asymptoticupper bound of minimum [r,R]-dominating set, and prove that [r,r +1]-domination numberwould not exceed d/((d - 2)(d - 1)^d/(d-2) asymptotically when r is large enough. Meanwhile,we point out an error of calculation in one of our major references.Finally, we end this thesis with outlooks on [r,R]-dominating set in future.