Resolvable path designs
Loading...
Files
Date
1983
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A resolvable (balanced) path design, RBPD (v,k,) is the decomposition of λ copies of the complete graph on v vertices into edge-disjoint subgraphs such that each subgraph consists of v /k vertex-disjoint paths of length k-1 (k vertices). It is shown that an RBPD (v,3,λ) exists if and only if v = 9 (modulo 12/gcd(4,λ)), Moreover, the RBPD (v,3,λ) can have an automorphism of order v/3. For k > 3, it is shown that if v is large enough, then an RBPD (v,k,1) exists if and only if v = k2 (modulo 1cm(2k-2,k)). Also, it is shown that the categorical product of a k-factorable graph and a regular graph is also k-factorable. These results are stronger than two conjectures of Hell and Rosa.