H.D.O.-F. Gronau, V. Leck, R.C. Mullin, P.J. Schellenberg
On Orthogonal Covers of $\vec{K_n}$
Preprint series: Preprints aus dem Fachbereich Mathematik, Universitt Rostock
MSC:
05C70 Factorization, matching, covering and packing
Abstract: An orthogonal cover of the complete digraph $\vec{K}_n$ is a
collection of $n$ spanning subgraphs
$\vec{G}_1$, $\vec{G}_2$, ..., $\vec{G}_n$
of $\vec{K}_n$ such that \\
{\bf -} every directed edge of $\vec{K}_n$ belongs to exactly 1 of
the $\vec{G}_i$'s and \\
{\bf -} for every two digraphs $\vec{G}_i$ and $\vec{G}_j$ $(i \neq j)$
there is a unique two-element set $\{a, b\}$ of vertices such that
$\vec{G}_i$ contains the directed edge $(a, b)$ and $\vec{G}_j$
contains the directed edge $(b, a)$. \\
It is proven that there exists an orthogonal cover of $\vec{K}_n$,
where the $\vec{G}_i$'s consist of short directed cycles, for
all $n \geq 4,$ with a few possible exceptions. We conclude by
establishing the existence of an orthogonal cover of $\vec{K}_n$,
where the $\vec{G}_i$'s have maximum outdegree and maximum indegree
one, for all $n \geq 2$. This gives another proof of the directed version of a
problem of Chung and West.

Keywords: orthogonal, cover, factorization