✦ LIBER ✦

Orthogonal double covers of general graphs

✍ Scribed by Sven Hartmann; Ulrike Schumacher

Publisher: Elsevier Science
Year: 2004
Tongue: English
Weight: 344 KB
Volume: 138
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(03)00274-9

No coin nor oath required. For personal study only.

✦ Synopsis

Let H be a graph on n vertices and G a collection of n subgraphs of H , one for each vertex. Then G is an orthogonal double cover (ODC) of H if every edge of H occurs in exactly two members of G and any two members share an edge whenever the corresponding vertices are adjacent in H . ODCs of complete graphs have been widely studied in literature. In this paper we are concerned with ODCs of arbitrary graphs. In particular, we investigate the existence of ODCs whose members are isomorphic sets of independent edges.

📜 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:

Counting double covers of graphs

✍ M. Hofmeister 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB

Any group of automorphisms of a graph G induces a notion of isomorphism between double covers of G. The corresponding isomorphism classes will be counted.

On orthogonal double covers by trees

✍ Uwe Leck; Volker Leck 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

A collection P of n spanning subgraphs of the complete graph Kn is said to be an orthogonal double cover (ODC) if every edge of Kn belongs to exactly two members of P and every two elements of P share exactly one edge. We consider the case when all graphs in P are isomorphic to some tree G and impro

Perfect path double covers of graphs

✍ J. A. Bondy 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 513 KB

## Abstract A __perfect path double cover__ (PPDC) of a graph __G__ on __n__ vertices is a family 𝒫 of __n__ paths of __G__ such that each edge of __G__ belongs to exactly two members of 𝒫 and each vertex of __G__ occurs exactly twice as an end of a path of 𝒫. We propose and study the conjecture th

Orthogonal double covers by super-extend

Orthogonal double covers by super-extendable cycles

✍ Christian Bey; Sven Hartmann; Uwe Leck; Volker Leck 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

## Abstract An Orthogonal Double Cover (ODC) of the complete graph __K__~__n__~ by an almost‐hamiltonian cycle is a decomposition of 2__K__~__n__~ into cycles of length __n__−1 such that the intersection of any two of them is exactly one edge. We introduce a new class of such decompositions. If __n

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.