# 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$$.

##### MSC:
 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:
##### References:
  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  Andersen, L.D.; Hilton, A.J.W., Generalized Latin rectangles I: construction and decomposition, Discrete Math., 31, 125-152, (1980) · Zbl 0443.05019  Andersen, L.D.; Hilton, A.J.W., Generalized Latin rectangles II: embedding, Discrete Math., 31, 235-260, (1980) · Zbl 0476.05018  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  Bahmanian, M.A., Rodger, C.A.: Multiply balanced edge colorings of multigraphs. J. Graph Theory. doi:10.1002/jgt.20617 · Zbl 1244.05085  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  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  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  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  Hall, M., An existence theorem for Latin squares, Bull. Am. Math. Soc., 51, 387-388, (1945) · Zbl 0060.02801  Hilton, A.J.W., Hamiltonian decompositions of complete graphs, J. Comb. Theory B, 36, 125-134, (1984) · Zbl 0542.05044  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  Hilton, A.J.W.; Rodger, C.A., Hamiltonian decompositions of complete regular $$s$$-partite graphs, Discrete Math., 58, 63-78, (1986) · Zbl 0593.05047  Laskar, R.; Auerbach, B., On decomposition of $$r$$-partite graphs into edge-disjoint Hamilton circuits, Discrete Math., 14, 265-268, (1976) · Zbl 0322.05128  Lindner, C.C.; Rodger, C.A., Generalized embedding theorems for partial Latin squares, Bull. Inst. Comb. Appl., 5, 81-99, (1992) · Zbl 0829.05014  Lucas E.: Récréations Mathématiques. vol. 2. Gauthiers Villars, Paris (1883)  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  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  S̆ajna, M.: Cycle decompositions of $$K$$_{$$n$$} and $$K$$_{$$n$$}−$$I$$. PhD Thesis Simon Fraser University (1999) · Zbl 1028.05083  S̆ajna, M., Cycle decompositions III: complete graphs and fixed length cycles, J. Comb. Des., 10, 27-78, (2002) · Zbl 1033.05078  Tarsi, M., On the decomposition of a graph into stars, Discrete Math., 36, 299-304, (1981) · Zbl 0467.05054  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.