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