Amalgamations of factorizations of complete equipartite graphs
type: Item
instance of: scholarly article
title: Amalgamations of factorizations of complete equipartite graphs
zbMATH Open document ID: 1057.05065
author: Matthew Johnson
author: A. J. W. Hilton
published in: Discrete Mathematics
publication date: 2004-08-20T00:00:00Z
review text: Let \(t\) be a positive integer and let \(K=(k_1,\dots,k_t)\) and \(L=(\ell_1,\dots,\ell_t)\) be sequences of nonnegative integers. We say that a graph \(G\) has a \((t,K,L)\)-factorization if the edge set of \(G\) can be partitioned into \(t\) subsets inducing factors \(F_1,\dots,F_t\) of \(G\) such that, for \(i=1,\dots,t\), \(F_i\) is \(k_i\)-regular and the edge-connectivity of \(F_i\) is at least \(\ell_i\). Let \(K_n^{(s)}\) be the complete \(s\)-partite graph with \(n\) vertices in each part. Here is the main result of the paper. The graph \(K_n^{(s)}\) has a \((t,K,L)\)-factorization if and only if \(\sum_{i=1}^tk_i=n(s-1);\) if \(ns\) is odd then each \(k_i\) is even; for \(1\leq i\leq t\), \(\ell_i\leq k_i\); and \(\ell_i=0\) if \(k_i=1\). The authors also show when a factorization of a complete \(\sigma\)-partite graph can be embedded in a \((t,K,L)\)-factorization of \(K_n^{(s)}\), \(\sigma <s\), and when a factorization of \(K_{a,b}\) can be embedded in a \((t,K,L)\)-factorization of \(K_{n,n}\), where \(a,b\leq n\). To prove the results they use the technique of amalgamations of graphs.
reviewed by: Zbigniew Lonc
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 2093777
zbMATH Keywords: factorization
zbMATH Keywords: complete equipartite graph
zbMATH Keywords: amalgamation method
MaRDI profile type: Publication
full work available at URL: j.disc.2003.11.030
OpenAlex ID: W2028104895
Wikidata QID: Q114190816
cites work: Hamiltonian decompositions of complete graphs
cites work: An algorithm for finding factorizations of complete graphs
cites work: Amalgamations of connected \(k\)-factorizations.
cites work: Hamiltonian decompositions of complete regular s-partite graphs
cites work: Decompositions of Complete Graphs
cites work: On decomposition of r-partite graphs into edge-disjoint Hamilton circuits
cites work: Connected Detachments of Graphs and Generalized Euler Trails
cites work: Amalgamations of almost regular edge-colourings of simple graphs
cites work: Embedding edge‐colorings into 2‐edge‐connected k‐factorizations of kkn+1
DOI: 10.1016/J.DISC.2003.11.030
description: scientific article; zbMATH DE number 2093777