More orthogonal double covers of complete graphs by Hamiltonian paths |
| |
Authors: | Sven Hartmann |
| |
Affiliation: | a Department of Information Systems, Massey University, Palmerston North, New Zealand b Institut für Mathematik, Universität Rostock, Germany |
| |
Abstract: | An 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. |
| |
Keywords: | 05B15 05C70 |
本文献已被 ScienceDirect 等数据库收录! |
|