\((r,r+1)\)-factorizations of \((d,d+1)\)-graphs (Q2470430): Difference between revisions
From MaRDI portal
Latest revision as of 16:54, 27 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \((r,r+1)\)-factorizations of \((d,d+1)\)-graphs |
scientific article |
Statements
\((r,r+1)\)-factorizations of \((d,d+1)\)-graphs (English)
0 references
14 February 2008
0 references
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.
0 references
graph
0 references
regular
0 references
semiregular
0 references
factor
0 references
factorization
0 references