Connected (g, f)-factors

In this paper we study connected (g, f)-factors. We describe an algorithm to connect together an arbitrary spanning subgraph of a graph, without increasing the vertex degrees too much; if the algorithm fails we obtain information regarding the structure of the graph. As a consequence we give sufficient conditions for a graph to have a connected (g, f)-factor, in terms of the number of components obtained when we delete a set of vertices. As corollaries we can derive results of Win [S. Win, Graphs Combin 5 (1989), 201-205], Xu et al. [B. Xu, Z. Liu, and T. Tokuda, Graphs Combin 14 (1998), 393-395] and Ellingham and Zha [M. N. Ellingham and Xiaoya Zha, J Graph Theory 33 (2000), 125-137]. We show that a graph has a connected [a, b]-factor (b > a greater than or equal to 2) if the graph is tough enough; when b greater than or equal to a + 2, toughness at least (a - 1) + a/b-a2 suffices. We also show that highly edge-connected graphs have spanning trees of relatively low degree; in particular, an m-edge-connected graph G has a spanning tree T such that deg(T) (upsilon) less than or equal to 2 + [deg(G)(upsilon)/m] for each vertex upsilon. (C) 2002 John Wiley & Sons, Inc.