×

zbMATH — the first resource for mathematics

Hamiltonian decompositions of complete graphs. (English) Zbl 0542.05044
The paper presents a procedure for constructing all Hamiltonian decompositions of the complete graph \(K_{2n+1}\). The technique is then applied to find a necessary and sufficient condition for a decomposition of the edge set of \(K_ r\) (\(r\leq 2n)\) into n classes, each class consisting of disjoint paths to be extendible to a Hamiltonian decomposition of \(K_{2n+1}\) so that each of the classes forms part of a Hamilton cycle.
Reviewer: W.K.Chen

MSC:
05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersen, L.D; Hilton, A.J.W, Generalized Latin rectangles. I. construction and decomposition, Discrete math., 31, 125-152, (1980) · Zbl 0443.05019
[2] Andersen, L.D; Hilton, A.J.W, Generalized Latin rectangles. II. embedding, Discrete math., 31, 235-260, (1980) · Zbl 0476.05018
[3] Andersen, L.D; Hilton, A.J.W, Generalized Latin rectangles, (), 1-17 · Zbl 0876.05015
[4] Andersen, L.D; Hilton, A.J.W, Quelques théorèmes sur carrés latins généralisés (ou sur graphes complets équitablement colorés), (), 307-313, (3-4) · Zbl 0403.05015
[5] Berge, C, ()
[6] Hall, M, An existence theorem for Latin squares, Amer. math. monthly, 67, 958-961, (1960)
[7] Harary, F, ()
[8] Hilton, A.J.W, The reconstruction of Latin squares with applications to school timetabling and to experimental design, Math. programming stud., 13, 68-77, (1980) · Zbl 0438.05016
[9] Hilton, A.J.W, School timetables, (), 177-188 · Zbl 0493.90043
[10] Hilton, A.J.W; Rodger, C.A, Matchtables, Ann. discrete math., 15, 239-251, (1982)
[11] de Werra, D, Balanced schedules, INFOR—canad. J. oper. res. inform. process., 9, 230-237, (1971) · Zbl 0222.90026
[12] de Werra, D, A few remarks on chromatic scheduling, (), 337-342
[13] de Werra, D, On a particular conference scheduling problem, INFOR—canad. J. oper. res. inform. process., 13, 308-315, (1975) · Zbl 0352.90032
[14] Wilson, R.J, ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.