More orthogonal double covers of complete graphs by Hamiltonian paths

An orthogonal double cover (ODC) of the complete graph KnKn by a graph G   is a collection GG of n   spanning subgraphs of KnKn, all isomorphic to G  , such that any two members of GG share exactly one edge and every edge of KnKn is contained in exactly two members of GG. In the 1980s 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-1n-1. It is known that the existence of an ODC of KnKn by a Hamiltonian path implies the existence of ODCs of K4nK4n and of K16nK16n, respectively, by almost-Hamiltonian cycles. Horton and Nonay introduced two-colorable ODCs and showed: If there are an ODC of KnKn by a Hamiltonian path for some n⩾3n⩾3 and a two-colorable ODC of KqKq by a Hamiltonian path for some prime power q⩾5q⩾5, then there is an ODC of KqnKqn by a Hamiltonian path. In [U. Leck, A class of 22-colorable orthogonal double covers of complete graphs by hamiltonian paths, Graphs Combin. 18 (2002) 155–167], two-colorable ODCs of KnKn and K2nK2n, respectively, by Hamiltonian paths were constructed for all odd square numbers n⩾9n⩾9. Here we continue this work and construct cyclic two-colorable ODCs of KnKn and K2nK2n, respectively, by Hamiltonian paths for all n   of the form n=4k2+1n=4k2+1 or n=(k2+1)/2n=(k2+1)/2 for some integer k.