We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science


Publication details for Professor Matthew Johnson

Hilton, A. J. W. & Johnson, Matthew. (2004). Amalgamations of factorizations of complete equipartite graphs. Discrete Mathematics 284(1-3): 157-175.

Author(s) from Durham


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 i=1,...,t 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. Our proofs use the technique of amalgamations of graphs.