✦ LIBER ✦

On DRC-covering of Kn by cycles

✍ Scribed by Jean-Claude Bermond; David Coudert; Min-Li Yu

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 173 KB
Volume: 11
Category: Article
ISSN: 1063-8539
DOI: 10.1002/jcd.10040

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

This paper considers the cycle covering of complete graphs motivated by the design of survivable WDM networks, where the requests are routed on INF‐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~n~, where V(K~n~) = V(G), such that each cycle in the covering satisfies the disjoint routing constraint (DRC7rpar;, relatively to G, which can be stated as follows: to each edge of K~n~ we associate in G a path and all the paths associated to the edges of a cycle of the covering must be vertex disjoint. Here we consider the case where G = C~n~, a ring of size n and we want to minimize the number of cycles in the covering. We give optimal solutions for the problem as well as for variations of the problem, namely, its directed version and the case when the cycle length is fixed to 4. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 100–112, 2003; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/jcd.10040

📜 SIMILAR VOLUMES

Orthogonal double covers of Kn,n by smal

Orthogonal double covers of Kn,n by small graphs

✍ Ramadan El-Shanawany; Hans-Dietrich O.F. Gronau; Martin Grüttmüller 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 443 KB

An orthogonal double cover (ODC) of Kn is a collection of graphs such that each edge of Kn occurs in exactly two of the graphs and two graphs have precisely one edge in common. ODCs of Kn and their generalizations have been extensively studied by several authors (e.g. in:

On a problem of Hering concerning orthog

On a problem of Hering concerning orthogonal covers of Kn

✍ A Granville; H.-D.O.F Gronau; R.C Mullin 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 265 KB

Covering the vertices of a graph by cycl

Covering the vertices of a graph by cycles of prescribed length

✍ D. Amar; I. Fournier; A. Germa 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 321 KB

The main theorem of that paper is the following: let G be a graph of order n, of size at least (nZ -3n + 6 ) / 2 . For any integers k, n,, n2,. . . , nk such that n = n, + n2 + ... + nk and n, 2 3, there exists a covering of the vertices of G by disjoint cycles (C,),=,..,k with ICjl = n,, except whe

Covering the vertices of a digraph by cy

Covering the vertices of a digraph by cycles of prescribed length

✍ D. Amar; A. Raspaud 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 427 KB

the vertices of a digraph by cycles of prescribed length, Discrete Mathematics 87 (

On cycle double covers of line graphs

✍ Leizhen Cai; Derek Corneil 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 257 KB

It is shown that if a graph has a cycle double cover, then its line graph also has a cycle double cover. The converse of this result for 2-edge-connected graphs would imply the truth of the cycle double cover conjecture. Cycle Double Cover Conjecture (CDCC). Every 2-edge-connected graph has a CDC.

On orthogonal double covers of kn and a

On orthogonal double covers of kn and a conjecture of chung and west

✍ H.-D. O. F. Gronau; R. C. Mullin; P. J. Schellenberg 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 909 KB

A collection = {GI, CZ, . . . , C,} of spanning subgraphs of K, is called an orthogonal double cover if (i) every edge of K , belongs to exactly two of the Ci's and (ii) any two distinct Ci's intersect in exactly one edge. Chung and West conjectured that there exists an orthogonal double cover of K,