zbMATH — the first resource for mathematics

Embedding an edge-colored \(K(a^{(p)};\lambda,\mu)\) into a Hamiltonian decomposition of \(K(a^{(p+r)};\lambda,\mu)\). (English) Zbl 1268.05050
Summary: Let \(K(a^{(p)};\lambda,\mu)\) be a graph with \(p\) parts, each part having size \(a\), in which the multiplicity of each pair of vertices in the same part (in different parts) is \(\lambda\) (\(\mu\), respectively). In this paper we consider the following embedding problem: When can a graph decomposition of \(K(a^{(p)};\lambda,\mu)\) be extended to a Hamiltonian decomposition of \(K(a^{(p+r)};\lambda,\mu)\) for \(r>0\)? A general result is proved, which is then used to solve the embedding problem for all \(r\geq\frac{\lambda}{\mu a}+\frac{p-1}{a-1}\). The problem is also solved when \(r\) is as small as possible in two different senses, namely when \(r=1\) and when \(r=\frac{\lambda}{\mu a}-p+1\).

05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
05C51 Graph designs and isomorphic decomposition
05C38 Paths and cycles
Full Text: DOI
[1] Alspach, B.; Gavlas, H., Cycle decompositions of \(K\)_{\(n\)} and \(K\)_{\(n\)} − \(I\), J. Combin. Theory Ser. B, 81, 77-99, (2001) · Zbl 1023.05112
[2] Andersen, L.D.; Hilton, A.J.W., Generalized Latin rectangles I: construction and decomposition, Discrete Math., 31, 125-152, (1980) · Zbl 0443.05019
[3] Andersen, L.D.; Hilton, A.J.W., Generalized Latin rectangles II: embedding, Discrete Math., 31, 235-260, (1980) · Zbl 0476.05018
[4] Andersen, L.D.; Rodger, C.A., Decompositions of complete graphs: embedding partial edge-colourings and the method of amalgamations, Surveys in Combinatorics Lond Math Soc Lect Note Ser, 307, 7-41, (2003) · Zbl 1028.05083
[5] Bahmanian, M.A., Rodger, C.A.: Multiply balanced edge colorings of multigraphs. J. Graph Theory. doi:10.1002/jgt.20617 · Zbl 1244.05085
[6] Bose, R.C.; Shimamoto, T., Classification and analysis of partially balanced incomplete block designs with two associate classes, J. Am. Statist. Assoc., 47, 151-184, (1952) · Zbl 0048.11603
[7] Fu, H.L.; Rodger, C.A., Group divisible designs with two associate classes: \(n\) = 2 or \(m\) = 2, J. Comb. Theory Ser. A, 83, 94-117, (1998) · Zbl 0911.05024
[8] Fu, H.L.; Rodger, C.A., 4-cycle group-divisible designs with two associate classes, Comb. Probab. Comput., 10, 317-343, (2001) · Zbl 0992.05030
[9] Fu, H.L.; Rodger, C.A.; Sarvate, D.G., The existence of group divisible designs with first and second associates, having block size 3, Ars Comb., 54, 33-50, (2000) · Zbl 0993.05018
[10] Hall, M., An existence theorem for Latin squares, Bull. Am. Math. Soc., 51, 387-388, (1945) · Zbl 0060.02801
[11] Hilton, A.J.W., Hamiltonian decompositions of complete graphs, J. Comb. Theory B, 36, 125-134, (1984) · Zbl 0542.05044
[12] Hilton, A.J.W.; Johnson, M.; Rodger, C.A.; Wantland, E.B., Amalgamations of connected \(k\)-factorizations, J. Comb. Theory B, 88, 267-279, (2003) · Zbl 1033.05084
[13] Hilton, A.J.W.; Rodger, C.A., Hamiltonian decompositions of complete regular \(s\)-partite graphs, Discrete Math., 58, 63-78, (1986) · Zbl 0593.05047
[14] Laskar, R.; Auerbach, B., On decomposition of \(r\)-partite graphs into edge-disjoint Hamilton circuits, Discrete Math., 14, 265-268, (1976) · Zbl 0322.05128
[15] Lindner, C.C.; Rodger, C.A., Generalized embedding theorems for partial Latin squares, Bull. Inst. Comb. Appl., 5, 81-99, (1992) · Zbl 0829.05014
[16] Lucas E.: Récréations Mathématiques. vol. 2. Gauthiers Villars, Paris (1883)
[17] Nash-Williams, C.St.J.A., Amalgamations of almost regular edge-colourings of simple graphs, J. Comb. Theory B, 43, 322-342, (1987) · Zbl 0654.05031
[18] Rodger, C.A.; Wantland, E.B., Embedding edge-colorings into 2-edge-connected \(k\)-factorizations of \(K\)_{kn+1}, J. Graph Theory, 19, 169-185, (1995) · Zbl 0815.05050
[19] S̆ajna, M.: Cycle decompositions of \(K\)_{\(n\)} and \(K\)_{\(n\)}−\(I\). PhD Thesis Simon Fraser University (1999) · Zbl 1028.05083
[20] S̆ajna, M., Cycle decompositions III: complete graphs and fixed length cycles, J. Comb. Des., 10, 27-78, (2002) · Zbl 1033.05078
[21] Tarsi, M., On the decomposition of a graph into stars, Discrete Math., 36, 299-304, (1981) · Zbl 0467.05054
[22] Tarsi, M., Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed designs, J.Comb. Theory Ser. A, 34, 60-70, (1983) · Zbl 0511.05024
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.