✦ LIBER ✦

Connected (g, f)-factors

✍ Scribed by M. N. Ellingham; Yunsun Nam; Heinz-Jürgen Voss

Publisher: John Wiley and Sons
Year: 2001
Tongue: English
Weight: 129 KB
Volume: 39
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10019

No coin nor oath required. For personal study only.

✦ Synopsis

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 deg~T~ (υ) ≤ 2 + ⌈ deg~G~(υ)/m⌉ for each vertex υ. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 62–75, 2002

📜 SIMILAR VOLUMES

Parity results on connected ƒ-factors

✍ Kenneth A. Berman 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 531 KB

Let G be a connected graph with vertex set V and let d(v) denote the degree of a vertex v ~ V. For f a mapping from V to the positive integers, an f-factor is a spanning subgraph having degree f(v) at vertex v. In this paper we extend the parity results of Thomason [2] on Hamiltonian circuits to con

Maximum (g,f)-factors of a general graph

✍ William Y.C. Chen 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 472 KB

Chen, W. Y. C., Maximum (g, f)-factors of a general graph, Discrete Mathematics 91 (1991) l-7. This paper presents a characterization of maximum (g, f)-factors of a general graph in which multiple edges and loops are allowed. An analogous characterization of the minimum (g,f)-factors of a general gr

A simple existence criterion for (g < f)

A simple existence criterion for (g < f)- factors

✍ Katherine Heinrich; Pavol Hell; David G. Kirkpatrick; Guizhen Liu 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 312 KB

We simplify the criterion of Lovasz for the existence of a (g, f)-factor when g <f, or when the graph is bipartite. Moreover, we give a simple direct proof, implying an O(m. IQ) algorithm, for these cases. We then illustrate the convenience of the new criterion by deriving some old and some new fact

Orthogonal (g, f)-factorizations in netw

Orthogonal (g, f)-factorizations in networks

✍ Peter Che Bor Lam; Guizhen Liu; Guojun Li; Wai Chee Shiu 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 96 KB 👁 1 views

Let G G G = (V V V, E E E) be a graph and let g g g and f f f be two integervalued functions defined on V V V such that k k k ≤ ≤ ≤ g g g(x x x) ≤ ≤ ≤ f f f(x x x) for all x x x ∈ ∈ ∈ V

Orthogonal (g,f)-factorizations in graph

Orthogonal (g,f)-factorizations in graphs

✍ Guizhen Liu 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 362 KB

LetGbeagraphandletF={F,,F,,..., F,,,} and H be a factorization and a subgraph of G, respectively. If H has exactly one edge in common with Fi for all i, 1 < i < m, then we say that F is orthogonal to H. Let g andf be two integer-valued functions defined on V(G) such that g(x) < f(x) for every x E V(

A Characterization of Graphs Having All

A Characterization of Graphs Having All (g, f)-Factors

✍ Thomas Niessen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 310 KB

Let G be a graph with vertex set V and let g, f : V Ä Z + . We say that G has all ( g, f )-factors if G has an h-factor for every h: V Ä Z + such that g(v) h(v) f (v) for every v # V and at least one such h exists. In this note, we derive from Tutte's f-factor theorem a similar characterization for