zbMATH — the first resource for mathematics

Hamiltonian decompositions of complete regular s-partite graphs. (English) Zbl 0593.05047
Generalizing a method of the first author [Hamiltonian decompositions of complete graphs, J. Comb. Theory, Ser. B 36, 125-134 (1984; Zbl 0542.05044)], the authors give a procedure by which Hamiltonian decompositions of the complete s-partite graph K(n,...,n) can be constructed whenever (s-1)n is even. The main effort is devoted to extending partial decompositions to Hamiltonian decompositions. Several theorems are presented, e.g.: If \(1\leq b\leq a\leq m\), then any proper edge-coloring of K(a,b) with m colors can be extended to a Hamiltonian decomposition of K(2m,2m).
Reviewer: J.Plesník

05C45 Eulerian and Hamiltonian graphs
05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[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 theorems sur carres latins generalises (ou sur graphes completesequitablement colores), (), 307-313, 3-4 · Zbl 0403.05015
[5] Berge, C., Graphs and hypergraphs, (1973), North-Holland Amsterdam · Zbl 0483.05029
[6] Harray, F., Graph theory, (1969), Addision-Wesley Reading, MA
[7] Hilton, A.J.W., The reconstruction of Latin squares with applications to school timetabling and to experimental design, Math. prog. study, 13, 68-77, (1980) · Zbl 0438.05016
[8] Hilton, A.J.W., School timetables, (), 177-188 · Zbl 0493.90043
[9] Hilton, A.J.W., Hamiltonian decompositions of complete graphs, J. combin.theory ser. A, 36, 125-134, (1984) · Zbl 0542.05044
[10] Hilton, A.J.W.; Rodger, C.A., Matchtables, Ann. discrete math., 15, 239-251, (1982)
[11] C. St. J.A. Nash-Williams, Connected detachments of graphs and generalized Euler trails, J. London Math. Soc., to appear. · Zbl 0574.05042
[12] Nash-Williams, C.St.J.A., Detachments of graphs and generalized Euler trails, (), to appear · Zbl 0574.05042
[13] Sotteau, D., Decomposition of \(K m,n (K m,n\^{}\{∗\})\) into cycles (circuits) of length 2k, J. combin. theory ser. B, 30, 75-81, (1981) · Zbl 0463.05048
[14] de Werra, D., Balanced schedules, Infor. journal, 9, 230-237, (1971) · Zbl 0222.90026
[15] de Werra, D., A few remarks on chromatic scheduling, (), 337-342
[16] de Werra, D., On a particular conference scheduling problem, Infor. journal, 13, 308-315, (1975) · Zbl 0352.90032
[17] Wilson, R.J., Introduction to graph theory, (1972), Oliver and Boyd Edinburgh · Zbl 0249.05101
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.