Amalgamations of factorizations of complete equipartite graphs.

Abstract

Let t be a positive integer, and let L=(l1,…,lt) and K=(k1,…,kt) be collections of nonnegative integers. A graph has a (t,K,L) factorization if it can be represented as the edge-disjoint union of factors F1,…,Ft where, for 1it, Fi is ki-regular and at least li-edge-connected. In this paper we consider (t,K,L)-factorizations of complete equipartite graphs. First we show precisely when they exist. Then we solve two embedding problems: we show when a factorization of a complete σ-partite graph can be embedded in a (t,K,L)-factorization of a complete s-partite graph, σ<s, and also when a factorization of Ka,b can be embedded in a (t,K,L)-factorization of Kn,n, a,bn. Our proofs use the technique of amalgamations of graphs.Let t be a positive integer, and let L=(l1,…,lt) and K=(k1,…,kt) be collections of nonnegative integers. A graph has a (t,K,L) factorization if it can be represented as the edge-disjoint union of factors F1,…,Ft where, for 1it, Fi is ki-regular and at least li-edge-connected. In this paper we consider (t,K,L)-factorizations of complete equipartite graphs. First we show precisely when they exist. Then we solve two embedding problems: we show when a factorization of a complete σ-partite graph can be embedded in a (t,K,L)-factorization of a complete s-partite graph, σ<s, and also when a factorization of Ka,b can be embedded in a (t,K,L)-factorization of Kn,n, a,bn. Our proofs use the technique of amalgamations of graphs.