More orthogonal double covers of complete graphs by Hamiltonian paths
- 作者：Sven Hartmann ; Uwe Leck ; Volker Leck
- 关键词：Orthogonal double cover ; ODC ; Graph decomposition ; Self-orthogonal decomposition
- 刊名：Discrete Mathematics
- 出版年：2008
- 期刊代码：47_0012365x
- 类别：cp
- 出版时间：28 June 2008
- 卷：308
- 期：12
- 页码：2502-2508
- 文件大小：163 K
摘要
An orthogonal double cover (ODC) of the complete graph Kn by a graph G is a collection 
of n spanning subgraphs of Kn, all isomorphic to G, such that any two members of 
share exactly one edge and every edge of Kn is contained in exactly two members of 
. 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 e885a84" title="Click to view the MathML source" alt="Click to view the MathML source">q5, 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 11e8e3310ccf8ec67cad8c9b68c73" title="Click to view the MathML source" alt="Click to view the MathML source">K2n, respectively, by Hamiltonian paths were constructed for all odd square numbers n9. 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.
3 and a two-colorable ODC of Kq by a Hamiltonian path for some prime power e885a84" title="Click to view the MathML source" alt="Click to view the MathML source">q5, 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 11e8e3310ccf8ec67cad8c9b68c73" title="Click to view the MathML source" alt="Click to view the MathML source">K2n, respectively, by Hamiltonian paths were constructed for all odd square numbers n9. 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.