Degree bounded factorizations of bipartite multigraphs and of pseudographs
by
Anthony Hilton
Queen Mary University of London

For d ≥ 1, s ≥ 0  a (d, d+s)-graph is a graph whose degrees all lie in the interval {d, d+1, ..., d+s}. For r ≥ 1, a ≥ 0  an (r, r+a)-factor of a graph G is a spanning (r, r+a)-subgraph of G. An (r, r+a)-factorization of a graph G is a decomposition of G into edge-disjoint (r, r+a)-factors.

We prove a number of results about (r, r+a)-factorizations of (d, d+s)-bipartite multigraphs and of (d, d+s)-pseudographs (multigraphs with loops permitted). For example, for t ≥ 1 let b(r, s, a, t) be the least integer such that, if d ≥ b(r, s, a, t) then every (d, d+s)-bipartite multigraph G has an (r, r+a)-factorization into x (r, r+a)-factors for at least t different values of x. Then we show that

b(r, s, a, t) = r é ê tr+s-1 a ù ú + (t-1)r .

Similarly for t ≥ 1 let p(r, s, a, t) be the least integer such that if d ≥ p(r, s, a, t) then each (d, d+s)-pseudograph has an (r, r+a)-factorization into x (r, r+a)-factors for at least t different values of x. We show that, if r and a are even, then p(r, s, a, t) is given by the same formula.

We use this to give bounds for p(r, s, a, t) when r and a are not both even. Finally we consider the corresponding functions for multigraphs without loops, and for simple graphs.

AMS Classification Number 05C70

Keywords. [a, b]-factorizations, nearly regular graphs

Date received: April 15, 2008