**Dalibor Froncek, Uwe Leck**

**Orthogonal double covers of complete graphs by fat caterpillars**

**Preprint series:**
Preprints aus dem Fachbereich Mathematik, Universität Rostock

**MSC:**- 05B40 Packing and covering, See also {11H31, 52C15, 52C17}
- 05C70 Factorization, matching, covering and packing

**Abstract:** An orthogonal double cover (ODC) of the complete graph $K_n$ by some graph $G$ is a collection of $n$ spanning subgraphs of $K_n$, all isomorphic to $G$, such that any two of the subgraphs share exactly one edge and every edge of $K_n$ is contained in exactly two of the subgraphs. A necessary condition for such an ODC to exist is that $G$ has exactly $n-1$ edges. We show that for any given positive integer $d$, all but finitely many caterpillars of diameter $d$ admit an ODC of the corresponding complete graph.

**Keywords:** *ODC, orthogonal double cover, graph decomposition, self-orthogonal factorization*

**Created:** 07 Feb 2005

**Updated:** 06 Apr 2005