\((r,r+1)\)-factorizations of \((d,d+1)\)-graphs (Q2470430): Difference between revisions

A \((d,d+1)\)-graph is a graph all of whose vertices have degrees in the set \([d,d+1]\). Such a graph is \textit{semiregular}. An \((r,r+1)\)-factorization of a graph \(G\) is a decomposition of \(G\) into \((r,r+1)\)-factors. For \(d\)-regular simple graph \(G\) we determine for which \(x\) and \(r\) \(G\) must have an \((r,r+1)\)-factorization with exactly \(x\) \((r,r+1)\)-factors. Similar results are given for \((d,d+1)\)-simple graphs and for \((d,d+1)\)-pseudographs. It is also demonstrated that if \(d\geq 2r^2 + 3r - 1\) then any \((d,d+1)\)-multigraph (without loops) has an \((r,r+1)\)-factorization and is given some information as to the number of \((r,r+1)\)-factors which can be found in an \((r,r+1)\)-factorization.