More orthogonal double covers of complete graphs by Hamiltonian paths (Q2427509)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | More orthogonal double covers of complete graphs by Hamiltonian paths |
scientific article |
Statements
More orthogonal double covers of complete graphs by Hamiltonian paths (English)
0 references
13 May 2008
0 references
A 2-colorable orthogonal double cover (ODC) of the complete graph \(K_n\) by Hamiltonian paths is a collection \(S\) of properly 2-colored Hamiltonian paths by the same two colors so that each two paths of \(S\) share exactly one edge, and each edge of \(K_n\) is covered by exactly two edges from \(S\) of the same color. In the paper a 2-colorable ODC of \(K_n\) and \(K_{2n}\) by Hamiltonian paths is constructed for all \(n = 4k^2+1\) and \(n = (k^2+1)/2\), \(k\in\mathbb{Z}\), respectively.
0 references
Orthogonal double cover
0 references
Graph decomposition
0 references