Orthogonal double covers by super‐extendable cycles

An Orthogonal Double Cover (ODC) of the complete graph K n by an almost‐hamiltonian cycle is a decomposition of 2 K 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‐hamiltonian cycle for primes p of order 3 mod 4 and its eventual existence for arbitrary primes p . © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 283–293, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10011