Christian Bey, Sven Hartmann, Uwe Leck, Volker Leck
Orthogonal double covers by super-extendable cycles
Preprint series: Preprints aus dem Fachbereich Mathematik, Universität Rostock
MSC:
05C70 Factorization, matching, covering and packing
05B40 Packing and covering, See also {11H31, 52C15, 52C17}
Abstract: An Orthogonal Double Cover (ODC) of the complete graph
K_n by an almost hamiltonian cycle is a decomposition of
2K_n into cycles of length n-1 such that the intersection
of any two of them is exactly one edge.
We introduce a new class of such decompositions.
If n is a prime, the special structure of such a
decomposition allows to expand it to an ODC of K_{n+1} by
an almost hamiltonian cycle. This yields the existence of
an ODC of K_{p+1} by an almost hamiltonain cycle for
primes p of order 3 mod 4 and its eventual existence for
arbitrary primes p.

Keywords: edge decomposition; ODC; cycle; asymptotic existence