H.-D.O.F. Gronau, R.C. Mullin, P.J. Schellenberg
On Orthogonal Double Covers of $\vec{K}_n$ and a Conjecture of Chung and West
Preprint series: Preprints aus dem Fachbereich Mathematik, Universitt Rostock

MSC:

05A05 Combinatorial choice problems (subsets, representatives, permutations)

Abstract: A collection ${\cal G}={G_1, G_2, ... ,G_n}$ of spanning subgraphs of
$K_n$
is called an {\cal orthogonal double cover} if (i) every edge of $K_n$
belongs to exactly two of the $G_i$'s and (ii) any two distinct $G_i$'s
intersect in exactly one edge. Chung and West conjectured that there
exists an orthogonal double cover of $K_n$ for all $n$, in wich each
$G_i$ has maximum degree 2, and proved this result for $n$ in six of
the residue classes modulo 12. In anover context, Ganter and Gronau
showed that for $n\equiv 1 \mbox{ mod } 3$, $n \not=10$, there exists
an orthogonal double cover of $K_n$ in wich each $G_i$ consists of an
isolated vertex and the vertex disjoint union of $K_3$'s (actually
these orthogonal double covers result from the solution of the
directed version of the problem, wich reduces to the undirected case
when the orientation of the arcs is ignored). Clearly the covers of
Ganter and Gronau satisfy the Chung-West requirement. In this paper,
the configurations of Ganter and Gronau are generalized to include the
cases $n \equiv 0,2 \mbox{ mod } 3$, and the results are used to
provide a
unified solution of the Chung-West problem.
For $n\not\equiv 5\mbox{ mod } 6$, all the spanning subgraphs in the
collection
${\cal G}$ are isomorphic to each other; however, this is not the case
when $n\not\equiv 5\mbox{ mod } 6$. In addition to solving the
Chung-West
problem, we also go on to show that for $n\equiv 2\mbox{ mod } 3$,
and $n>287$,
there exists an orthogonal double cover of $K_n$ in wich each spanning
subgraph $G_i$ consists of the vertex-disjoint union of an isolated
vertex, a quadrilateral, and $(n-5)/3$ triangels. Of the 96 cases with
$2\leq n \leq 287, 65$ cases are resolved and 31 remain open.
Keywords: designs, covers of graphs, orthogonal double covers