Amalgamations of connected \(k\)-factorizations.

*(English)*Zbl 1033.05084Let \(G\) be an edge-colored graph on the set of colors \(\{ 1,2,\ldots,n\}\), and let \(P\) be a partition of \(V(G)\). The \(P\)-amalgamation of \(G\) is the \(n\)-edge-colored graph with vertex set \(P\), in which \(p\in P\) is incident with \(y\) loops colored \(i\) if and only if there are \(y\) loops or edges in \(G\) that join vertices in \(p\), and in which the number of edges colored \(i\) joining \(p_1,p_2\in P\), \(p_1\not= p_2\), is the number of edges colored \(i\) in \(G\) that join vertices in \(p_1\) to vertices in \(p_2\). We say that \(H\) is an amalgamation of \(G\) if it is the \(P\)-amalgamation of \(G\) for some partition \(P\) of \(V(G)\). This paper contains two main results: (1) a necessary and sufficient condition for a graph with exactly one amalgamated vertex to be the amalgamation of a \(k\)-factorization of the complete graph \(K_{kn+1}\) in which each \(k\)-factor is connected, (2) a necessary and sufficient condition for a given edge-colored complete graph \(K_t\) to be embedded in a \(k\)-factorization of \(K_{kn+1}\) in which each \(k\)-factor is connected.

Reviewer: Zbigniew Lonc (Warszawa)

##### MSC:

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

05C15 | Coloring of graphs and hypergraphs |

PDF
BibTeX
XML
Cite

\textit{A. J. W. Hilton} et al., J. Comb. Theory, Ser. B 88, No. 2, 267--279 (2003; Zbl 1033.05084)

Full Text:
DOI

##### References:

[1] | Alspach, B; Gavlas, H, Cycle decompositions of Kn and kn−I, J. combin. theory B, 81, 77-99, (2001) · Zbl 1023.05112 |

[2] | Andersen, L.D; Hilton, A.J.W, Generalized Latin rectangles iiembedding, Discrete math., 31, 235-260, (1980) · Zbl 0476.05018 |

[3] | Andersen, L.D; Hilton, A.J.W; Mendelsohn, E, Embedding partial Steiner triple systems, Proc. London math soc., 41, 557-576, (1980) · Zbl 0461.05010 |

[4] | Doyen, J; Wilson, R.M, Embeddings of Steiner triple systems, Discrete math., 5, 229-239, (1973) · Zbl 0263.05017 |

[5] | Hanani, H, On quadruple systems, Canad. J. math., 12, 145-157, (1960) · Zbl 0092.01202 |

[6] | Hilton, A.J.W, Hamiltonian decompositions of complete graphs, J. combin. theory B, 36, 125-134, (1984) · Zbl 0542.05044 |

[7] | Hilton, A.J.W; Rodger, C.A, Hamiltonian decompositions of complete regular s-partite graphs, Discrete math., 48, 63-78, (1986) · Zbl 0593.05047 |

[8] | Hilton, A.J.W; Rodger, C.A, The embedding of partial triple systems when 4 divides λ, J. combin. theory A, 56, 109-137, (1991) · Zbl 0758.05022 |

[9] | A. Johansson, A note on extending partial triple systems, submitted for publication. |

[10] | Kirkman, Rev.T.P, On a problem in combinatorics, Cambridge Dublin math. J., 2, 191-204, (1847) |

[11] | Lindner, C.C; Rodger, C.A, Decompositions into cycles II: cycle systems, () · Zbl 0774.05078 |

[12] | Lindner, C.C; Rodger, C.A, A partial m=(2k+1)-cycle system of order n can be embedded in an m-cycle system of order (2n +1)m, Discrete math., 117, 151-159, (1993) · Zbl 0789.05006 |

[13] | Lindner, C.C; Rodger, C.A, Embedding directed and undirected partial cycle systems of index λ, J. combin. designs, 1, 113-123, (1993) · Zbl 0818.05029 |

[14] | Nash-Williams, C.St.J.A, Amalgamations of almost regular edge-colourings of simple graphs, J. combin. theory B, 43, 322-342, (1987) · Zbl 0654.05031 |

[15] | Nash-Williams, C.St.J.A, Connected detachments of graphs and generalized Euler trails, J. London math. soc., 31, 2, 17-29, (1985) · Zbl 0574.05042 |

[16] | Rodger, C.A; Wantland, E.B, Embedding edge-colourings into 2-edge-connected k-factorizations of kkn+1, J. graph theory, 19, 169-185, (1995) · Zbl 0815.05050 |

[17] | Sajna, M, Cycle decompositions iiicomplete graphs and fixed length cycles, J. combin. designs, 10, 27-78, (2002) · Zbl 1033.05078 |

[18] | Tarsi, M, Decompositions of complete multigraphs into stars, Discrete math., 26, 273-278, (1979) · Zbl 0421.05016 |

[19] | Tarsi, M, Decomposition of the complete multigraph into simple pathsnon-balanced handcuffed designs, J. combin. theory A, 34, 60-70, (1983) · Zbl 0511.05024 |

[20] | West, D, Introduction to graph theory, (1996), Prentice-Hall Englewood Cliffs, NJ · Zbl 0845.05001 |

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.