Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650763 | Discrete Mathematics | 2008 | 25 Pages |
Abstract
A (d,d+1)(d,d+1)-graph is a graph whose vertices all have degrees in the set {d,d+1}{d,d+1}. Such a graph is semiregular . An (r,r+1)(r,r+1)-factorization of a graph G is a decomposition of G into (r,r+1)(r,r+1)-factors. For d-regular simple graphs G we say for which x and r G must have an (r,r+1)(r,r+1)-factorization with exactly x (r,r+1)(r,r+1)-factors. We give similar results for (d,d+1)(d,d+1)-simple graphs and for (d,d+1)(d,d+1)-pseudographs. We also show that if d≥2r2+3r-1d≥2r2+3r-1, then any (d,d+1)(d,d+1)-multigraph (without loops) has an (r,r+1)(r,r+1)-factorization, and we give some information as to the number of (r,r+1)(r,r+1)-factors which can be found in an (r,r+1)(r,r+1)-factorization.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
A.J.W. Hilton,