Hamiltonian decompositions of complete graphs |
| |
Authors: | AJW Hilton |
| |
Institution: | Department of Mathematics, University of Reading, Whiteknights, Reading RG6 2AX, England |
| |
Abstract: | It is well known that K2n + 1 can be decomposed into n edge-disjoint Hamilton cycles. A novel method for constructing Hamiltonian decompositions of K2n + 1 is given and a procedure for obtaining all Hamiltonian decompositions of of K2n + 1 is outlined. This method is applied to find a necessary and sufficient condition for a decomposition of the edge set of Kr (r ≤ 2n) into n classes, each class consisting of disjoint paths to be extendible to a Hamiltonian decomposition of K2n + 1 so that each of the classes forms part of a Hamilton cycle. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|