Uwe Leck
A class of 2-colorable orthogonal double covers of complete graphs by hamiltonian paths
Preprint series: Preprints aus dem Fachbereich Mathematik, Universitt 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 a
graph $G$ is a collection $\mathcal{G}$ of $n$ spanning subgraphs of $K_n$,
all isomorphic to $G$, such that any two members of $\mathcal{G}$ share
exactly one edge and every edge of $K_n$ is contained in exactly two
members of $\mathcal{G}$. In the 1980's Hering posed the problem to decide
the existence of an ODC for the case that $G$ is an almost-hamiltonian
cycle, i.e.~a cycle of length $n-1$. It is known that the existence of
an ODC of $K_n$ by a hamiltonian path implies the existence of ODCs of
$K_{4n}$ and $K_{16n}$, respectively, by almost-hamiltonian cycles.
Horton and Nonay introduced 2-colorable ODCs and showed: If for $n\ge 3$
and a prime power $q\ge 5$ there are an ODC of $K_n$ by a hamiltonian path
and a 2-colorable ODC of $K_q$ by a hamiltonian path, then there is an
ODC of $K_{qn}$ by a hamiltonian path. We construct 2-colorable ODCs of
$K_n$ and $K_{2n}$, respectively, by hamiltonian paths for all odd square
numbers $n\ge 9$.
Keywords: orthogonal double cover, self-orthogonal 2-sequencings, Hering's problem