Sven Hartmann, Uwe Leck, Volker Leck
More orthogonal double covers of complete graphs by Hamiltonian paths
Preprint series: Preprints aus dem Fachbereich Mathematik, Universität Rostock
MSC:
05B15 Orthogonal arrays, Latin squares, Room squares
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 two-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 two-colorable ODC of $K_q$ by a Hamiltonian path, then there is an
ODC of $K_{qn}$ by a Hamiltonian path. In \cite{ul00}, two-colorable ODCs of
$K_n$ and $K_{2n}$, respectively, by Hamiltonian paths were constructed
for all odd square numbers $n\ge 9$. Here we continue this work and construct
cyclic two-colorable ODCs of $K_n$ and $K_{2n}$, respectively, by Hamiltonian
paths for all $n$ of the form $n=4k^2+1$ or $n=(k^2+1)/2$ with some
integer $k$.
Keywords: orthogonal double cover, ODC, graph decomposition, self-orthogonal decomposition