Research On Connected Dominating Partition In Regular Graphs

In wireless sensor network technology,virtual backbone network tech-nology has been widely studied as an important part of network commu-nication technology.From the perspective of network topology,a virtual backbone of a network can be implemented by constructing its connect-ed dominating set.The nodes of the connected dominating set in virtual backbone network have additional computational communication burdens,therefore,the rotation of the connected dominating set can not only balance the information load but also extend the battery life.By studying the the maximum number of a disjoint partition of vertex sets in the graph,the con-nected dominating partition of the graph provides the theoretical basis and implementation methods of the wireless network virtual backbone rotation technology.In this paper,we study the connected dominating partition of regular graphs,the details are as follows:Firstly,based on several known conclusions of connected dominat-ing sets,we study the connected dominating partition problem of gener-al graphs and regular graphs,then we give some basic lemmas.On the basis of above,we focus on the connected dominating partition of cubic graphs,we prove the necessary and sufficient conditions for a cubic graph that can be partitioned into two connected dominating sets and design a concrete construction method.We also study the relationship between the2-connected dominating partition and connectivity of cubic graphs,and we prove that there is a 3-connected cubic graph which can not be partitioned into two connected dominating sets.Secondly,we study the connected dominating partition problem for a class of classical special cubic graphs,generalized Petersen graphs P?n,k?.We prove that the generalized Petersen graph P?n,k?is 2-connected domi-nating partition when n and k are mutually prime,and P?2m,2?is 2-connected dominating partition when n and k are not mutually prime.In addition,we study the following basic types of generalized Petersen graphs,and we prove P?4m,3?,P?5m,3?are all 2-connected dominating partition.We also find and prove that the generalized Petersen graph P?9,3?can not be parti-tioned into two connected dominating sets.Finally,we study the connected dominating partition problem for an-other class of classical special regular graphs,circulant graphs.We take the circulant graph C_?2k+1?m?1,2,...,k,2k+1?as the research object,by dis-cussing the range of values of m,we get the following conclusions:there is a k-regular cubic graph that satisfies the?k-1?-connected dominating par-tition?or k-connected dominating partition or?k+1?-connected dominating partition?.