UDC 004.635, DOI: 10.2298/csis0902229L

Zhihe Liang

School of Mathematics and Information Science
Hebei Normal University
Shijiazhuang 050016, P. R. China
zhiheliang@163.com.cn

Abstract. This paper considers the cycle covering of complete multipartite 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 λΚ_t(n), where V(K_t(n))=V(G), such that each cycle in the covering satisfies the disjoint routing constraint (DRC). Here we consider the case where G=C_tn, a ring of size tn and we want to minimize the number of cycles ρ(n^t, λ)  in the covering. For the problem, we give the lower bound of ρ(n^t, λ), and obtain the optimal solutions when n is even or n is odd and both λ and t are even.