A Class of 2-Colorable Orthogonal Double Covers of Complete Graphs by Hamiltonian Paths

K _n by a graph G is a collection ? of n spanning subgraphs of K _n , all isomorphic to G, such that any two members of ? share exactly one edge and every edge of K _n is contained in exactly two members of ?. 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≥3 and a prime power q≥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≥9. Received: January 27, 2000