On solutions of Alspach's problems

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\).

Recommendations

Cited in

(9)

This page was built for publication: On solutions of Alspach's problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1334078)