Amalgamations of connected \(k\)-factorizations.
type: Item
instance of: scholarly article
title: Amalgamations of connected \(k\)-factorizations.
zbMATH Open document ID: 1033.05084
DOI: 10.1016/S0095-8956(03)00030-3
author: Matthew Johnson
author: C. A. Rodger
author: E. B. Wantland
author: A. J. W. Hilton
published in: Journal of Combinatorial Theory. Series B
publication date: 2003-08-17T00:00:00Z
review text: Let \(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.
reviewed by: Zbigniew Lonc
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1965033
zbMATH Keywords: edge-coloring
zbMATH Keywords: amalgamation
zbMATH Keywords: graph factorization
zbMATH Keywords: complete graph
MaRDI profile type: Publication
cites work: Cycle decompositions of \(K_n\) and \(K_n-I\)
cites work: Generalized latin rectangles. II: Embedding
cites work: Embedding Partial Steiner Triple Systems
cites work: Embeddings of Steiner triple systems
cites work: On Quadruple Systems
cites work: Hamiltonian decompositions of complete graphs
cites work: Hamiltonian decompositions of complete regular s-partite graphs
cites work: The embedding of partial triple systems when 4 divides \(\lambda\)
cites work: Q4026150
cites work: A partial \(m=(2k+1)\)-cycle system of order \(n\) can be embedded in an \(m\)- cycle of order \((2n+1)m\)
cites work: Embedding directed and undirected partial cycle systems of index λ > 1
cites work: Amalgamations of almost regular edge-colourings of simple graphs
cites work: Connected Detachments of Graphs and Generalized Euler Trails
cites work: Embedding edge‐colorings into 2‐edge‐connected k‐factorizations of kkn+1
cites work: Cycle decompositions. III: Complete graphs and fixed length cycles.
cites work: Decomposition of complete multigraphs into stars
cites work: Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed designs
cites work: Q4869540
description: scientific article; zbMATH DE number 1965033