Amalgamations of factorizations of complete equipartite graphs

DOI10.1016/J.DISC.2003.11.030MaRDI QIDQ1876684zbMATH OpenOpenAlexWikidataFDO

Authors Matthew Johnson, A. J. W. Hilton

Publication date 20 August 2004

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2003.11.030, https://durham-repository.worktribe.com/output/1580739

zbMATH Keywords

amalgamation method complete equipartite graph factorization

Mathematics Subject Classification ID

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

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.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Amalgamations of factorizations of complete equipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1876684)