Research On Total Domination In Generalized Petersen Graphs And Circulant Graphs

With the development of computer network,graph theory has become one active field of combinatorics.Domination in graph theory is a hot issue in recent years.It has a widespread and profound practical application of the optimization,design and analysis of communication networks,social sciences.When the dominating set of a graph has been restricted by some con-ditions,it will obtain a class of new domination-type problems,such as the total dominating set.A total dominating set of a graph G with no isolated vertex is a set S of vertices of G such that every vertex is adjacent to a ver-tex in S.A k-tuple total dominating set of a graph G is a set S of vertices of graph G such that every vertex of graph G has at least k neighbors in S.When k=2,it is called a double total dominating set.This thesis introduces total domination in generalized Petersen graphs P(n,k)and circulant graphs C_n(1,k).The total domination numbers and double total domination numbers of P(n,k)for k=1,2 are given.The total domination numbers of C_n(1,2)and C_n(1,3)are also studied.We also determine upper bounds on the total domination numbers of P(n,k)and C_n(1,k).Firstly,a general lower bound on the total domination number of a regular graph has been provided.Then the lower bound on the total dom-ination number of P(n,k)is obtained.Throughout constructing the total dominating sets of P(n,k),we study the exact values of total domination number for k=1,2.And their proofs are given by contradiction.If n and k are not triple,the upper bound on the total domination number of P(n,k)is given.Secondly,the lower bound on the double total domination number of P(n,k)is given.Using the same argument as in the proof of total domi-nation in P(n,k),the exact values of double total domination numbers of P(n,k)for k=1,2 are given.And we prove them by contradiction.Finally,we turn our attention to total domination in circulant graphs C_n(1,k).We then analyze the distribution of connected components with order two or three of C_n(1,k),respectively.Throughout constructing the total dominating sets of C_n(1,k),the exact values of total domination num-bers for k=2,3 are given.And their proofs are also given by contradiction.The upper bound on the total domination number of C_n(1,k)for odd k is given.