Research On Connected Domination In Some Graphs

This thesis mainly studies the connected and tree dominating sets in some graphs.Connected domination in graphs is one of the hot topics of graph theory recently.Research on connected domination in graphs has not only important theoretical significance,but also varied applications in such fields as the optimization theory,design and analysis of communica-tion networks,network search,pattern recognition,and many other fields.Especially,it plays a significant role of the connected dominating set in the application of wireless sensor networks,peer-to-peer networks,intercon-nection networks,and ad hoc sensor networks in recent years.In this thesis,we mainly calculate exact values of connected dominat-ing sets in some regular graphs with tree dominating set as a tool.The details are as follows.Firstly,we calculate the tree dominating sets of generalized Petersen graphs P(n,k)by algorithm and find the regular patterns of the tree domi-nating sets for different order n.And we pose the connected and tree dom-ination number of generalized Petersen graphs P(n,k)for k = 3,5,7.We also observe that there is a relationship among the circular sections of γtr-set of generalized Petersen graphs P(n,3),P(n,5),and P(n,7)with odd n.Secondly,we pose the bounds on the connected domination numbers of three classes of snarks with existing conclusions.We construct the tree dominating sets of three classes of snarks and make each tree domination number equal to the bound,thus we get the connected domination numbers of Goldberg snarks,Twisted Goldberg snarks,and Flower snarks.Finally,based on the properties of circulant graphs Cn(1,k),we study the connected domination numbers of circulant graphs Cn(1,k)with the lower bound on the connected domination number given by existing con-clusions.And we pose the connected domination numbers of circulant graphs Cn(1,k)for k = 2,3,4.We also analyze the connected dominat-ing sets of circulant graphs C,(1,k)for k=2,3,4 and study the connected dominating sets of circulant graphs Cn(1,k)for arbitrary k,thus we get the lower and upper bounds on the connected domination numbers of circulant graphs Cn(1,k).