Connected (g, f)‐factors
Mark N. Ellingham, Yunsun Nam, Heinz‐Jürgen Voss · Journal of Graph Theory · 2001
Abstract 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 ≥ 2) if the graph is tough enough; when b ≥ a + 2, toughness at least $(a-1) + {a\over b-2}$ 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 degT (υ) ≤ 2 + ⌈ degG(υ)/m⌉ for each vertex υ. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 62–75, 2002