More orthogonal double covers of complete graphs by Hamiltonian paths

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