Connected \((g,f)\)-factors (Q2778283)

Let \(G\) be a graph with vertexset \(V\). Denote by \(\deg_G(v)\) the degree of \(v\) in \(G\). A factor of \(G\) is a spanning subgraph of \(G\). If \(f\) and \(g\) are nonnegative integer-valued functions on \(V\) with \(f\geq g\), then a factor \(F\) is a \((g,f)\)-factor if \(g(v)\leq\deg_F(v)\leq f(v)\) for all \(v\) in \(V\). The paper studies the connected \((f,g)\)-factors by presenting an algorithm to connect together an arbitrary spanning subgraph of a graph without increasing the vertex degrees too much. If the algorithm fails, information regarding the structure of the graph is obtained. Based on this, it gives sufficient conditions for a graph to have a connected \((g,f)\)-factor in terms of the number of components obtained when a set of vertices is deleted.