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: | Export: EndNote, Zotero | BibTex |

Usage statistics | Look up in GoogleScholar | Find in a UK Library |