Premium
Connected ( g, f )‐factors
Author(s) -
Ellingham M. N.,
Nam Yunsun,
Voss HeinzJürgen
Publication year - 2002
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10019
Subject(s) - combinatorics , mathematics , spanning tree , discrete mathematics , vertex (graph theory) , graph , distance hereditary graph , connectivity , bound graph , graph power , line graph
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 deg T (υ) ≤ 2 + ⌈ deg G (υ)/ m ⌉ for each vertex υ. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 62–75, 2002