Factorizations of regular graphs of high degree

✍ Scribed by A. J. W. Hilton

• Publisher: John Wiley and Sons
• Year: 1985
• Tongue: English
• Weight: 168 KB
• Volume: 9
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190090116

✦ Synopsis

A p-factor of a graph G is a regular spanning subgraph of degree p . For G regular of degree d ( G ) and order 2n, let ( p l , ..., p,) be a partition of d ( G ) , so that p i > 0 ( I S i S r ) and p , i i pr = d(G). If H I . ..., H, are edge-disjoint regular spanning subgraphs of G of degrees p I , ..., p , , respectively, then we say that (HI, ..., H,) is a ( p l , ..., p,)-facrorization of G . If p 1 = ... = p , = p , then we say that ( H I , ..., H , ) is a pfuctorization of G .

. Petersen [3] showed that if d ( G ) is even then G has a 2-factorization. In [ 11, A. G. Chetwynd and the author considered the following conjecture.

Conjecture 1. Let G be a regular simple graph on 2n vertices of degree d

(G). If d ( G )

Although we were not able to prove this conjecture in general we were able to prove it for 2n -1 3 d ( G ) 3 2n -5. and for d ( G ) 2 '? n.

Conjecture 1 implies the following conjecture. n then G is I-factorizable. Conjecture 2. Let G be a regular simple graph on 2n vertices of degree d ( G ) . Let ( p l , ..., p,) be a partition of d ( G ) . If d ( G ) 3 n , thcn G has a ( p l , ..., p,)-factorization.

Clearly Conjecture I implies Conjecture 2, as one can combine p I 1factors to form a pl-factor, etc.

In this note we prove Conjecture 2 in a wide variety of cases, in fact whenever ( p l , ..., p , ) does not include too many 1's. We also show that Conjecture 2 is best possible in the sense that whcn n is odd then in general the lower bound on d ( G ) , namely, d ( G ) 2 n, cannot be lowered to d ( G ) 3 n -I [if n is even, then dlG) 3 n could be lowered to d ( G ) 2 n -1 but not to d ( G ) 2 n -2 in general].