Article contents
On Factors of a Graph
Published online by Cambridge University Press: 20 November 2018
Abstract
Let G be a graph with multiple edges. Let f be a function from the vertex set V(G) of G to the non-negative integers. An f-factor of G is a spanning subgraph F of G such that the degree (valence) of each vertex x in F is f(x). A theorem of Fulkerson, Hoffman and McAndrew [1] gives necessary and sufficient conditions to have an f-factor for a graph G with the odd-cycle property; i.e., if G has the property that either any two of its odd (simple) cycles have a common vertex, or there exists a pair of vertices, one from each cycle, which is joined by an edge. They proved this theorem using integer programming techniques, with a rather long proof. We show that this is a corollary of Tutte's f-factor theorem.
- Type
- Research Article
- Information
- Copyright
- Copyright © Canadian Mathematical Society 1977
References
- 5
- Cited by