On solutions of Alspach's problems (Q1334078)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On solutions of Alspach's problems |
scientific article |
Statements
On solutions of Alspach's problems (English)
0 references
7 March 1995
0 references
Let \(G\) be a graph and \(a \leq b\) integers. A spanning subgraph of \(G\) is called an \([a, b]\)-factor if for every vertex \(v\) we have \(a \leq d_ h (v) \leq b\), where \(d_ H(v)\) denotes the degree of vertex \(v\) in \(H\). Similarly are defined \([a, b]\)-graphs. The author solves the problem of the decomposition of a graph with given matching \(H\) into \([a, b]\)- factors \(F_ 1,\dots ,F_ m\) orthogonal to \(H\). The factorisation \(F=\{F_ 1,\dots ,F_ m\}\) is orthogonal to the matching \(H\) if \(| E (H) \cap E (F_ i) |= 1\) for \(i=1,\dots ,m\). It is proved that if \(G\) is an \([ma-1, mb+1]\)-graph then for an arbitrary matching \(H\) of \(G\) there exists an \([a-b, b+1]\)-factorisation orthogonal to \(H\). In some sense it is the best possible result as there exists a \([ma, mb]\)-graph with matching \(H\) not orthogonal to any factorisation of \(G\).
0 references
Alspach's problems
0 references
\([a, b]\)-graph
0 references
decomposition
0 references
matching
0 references
factorisation
0 references