DRC Cycle Covering Of Complete Multipartite Graph

This paper considers the cycle covering of complete graphs motivated by the design of survivable WDM networks,where the requests are routed on sub-networks which are protected independently from each other.The problem can be stated as follows:for a given graph G,find a cycle covering of the edge set ofλK_t(n),where V(λK_t(n)) = V(G),such that each cycle in the covering satisfies the disjoint routing constraint(DRC),relatively to G.In other words: to each edge ofλK_t(n) we associate inG a path and all the paths associated to the edges of a cycle of the covering must be vertex disjoint.We want to minimize the number of cycles in the covering.In,Bermond rised two problems:when we consider the case where G = C_n,a ring of size n and logical graph isλK_n orλK_n,n,how many cycles are needed at least? For the two problems,Liang Zhihe and Han Na gave optimal solutions as well as for variations of the problem,namely,its directed version.In this paper we give optimal solutions on the cycle covering ofλK_t(n)(n≡1(mod2),t≡1(mod 2),λ∈Z),that each cycle in the covering satisfies the disjoint routing constraint.