Amalgamations of factorizations of complete equipartite graphs (Q1876684): Difference between revisions

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.