Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Amalgamations of factorizations of complete equipartite graphs.

Hilton, A. J. W. and Johnson, Matthew. (2004) 'Amalgamations of factorizations of complete equipartite graphs.', Discrete mathematics., 284 (1-3). pp. 157-175.

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.

Item Type:Article
Full text:PDF - Accepted Version (260Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1016/j.disc.2003.11.030
Record Created:07 Oct 2009 11:20
Last Modified:25 Nov 2011 09:40

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library