Cookies

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

Profile

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

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 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.