Article ID Journal Published Year Pages File Type
4650763 Discrete Mathematics 2008 25 Pages PDF
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
,