The Minimum Semitotal Domination Set In Graphs

The domination problem in graphs is an important field of graph theory. In order to solve problems in actual applications of computer networks and logistics warehousing,kinds of domination sets are derived. In this paper, we study the semitotal domination number in graphs. It is an important domination parameter which is bounded by the domination number and the total domination number.The research of various domination problems in the cartesian product graph has been very active. We provide the semitotal domination number of cylindrical grid graph P_k?C_n with 2 ? k ? 5 by means of block and complete grid graph P_k?P_n with 2 ? k ? 5 by some properties and the mathematical induction.Moreover, we study the minimum semitotal dominating set problem in caterpillars and spider trees. For the problem, we present a algorithm to find the semitotal domination number of caterpillars and give the semitotal domination number of spider trees such as wounded spider, healthy spider, k-extended stars and so on.With the development of computer networks, unit disk graphs have been applied in many fields. They are widely used as a mathematical model for some problems in broadcast networks, wireless sensor networks and computational geometry. Finally, we present a 5-approximation algorithm based on the maximal independent set and a PTAS based on the 2-separated collection of subsets for the minimum semitotal domination set problem in unit disk graphs.