The Research On Related Problems Of Total Domination In Graphs

Total domination in graphs is one of the hotspots of graph theory,which has been widely used in optimization theory,network design and other fields.When the total dominating set of a graph has been restricted by some condition,it will produce a variety of derivative total dominating sets,such as double total dominating set and semitotal dominating set.This thesis introduces double total domination and semitotal domination in generalized Petersen graphs P(n,k),circulant graphs C_n(1,k)and cartesian product graphs.The specific research contents are as follows:(1)The structural characterization of the double total dominating sets of circulant graphs C_n(1,k)with smaller k and n and the cartesian product graphs C_m?C_n with m is odd are obtained by the algorithm.We Find out the periodic rule of double total dominating sets when n is different.We prove a necessary and sufficient for circulant graphs C_n(1,k)to admit efficient double total dominating sets.Combining the circulant graphs C_n(1,k)and cartesian product graphs C_m?C_nare four regular graphs,the lower bounds of their double total dominating sets are obtained.The exact values of circulant graphs C_n(1,k)for k=2,3,4,5 and Cartesian product graphs C_m?C_n are obtained and a corresponding double dominating sets are also determined.(2)We study the relationship between semitotal domination number and domination number,semitotal domination number and total domination number.Then propose an algorithm of the minimum semitotal dominating sets.The structural characterization of the semitotal dominating sets of the generalized Petersen graphs P(n,k)and circulant graphs C_n(1,k) with smaller k and n are obtained by the algorithm.We Find out the periodic rule of semitotal dominating sets when n is different.These lower bounds are obtained by subdividing the structure of the generalized Petersen graphs P(n,k)and circulant graphs C_n(1,k) in various cases based on the definition of the repeated domination number.The exact values of generalized Petersen graphs P(n,k)for k=1,2 and circulant graphs C_n(1,k)for k=2,3 are obtained and a corresponding semitotal dominating sets are also determined.