Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-25T18:28:42.338Z Has data issue: false hasContentIssue false
  • English
  • Français

On Factors of a Graph

Published online by Cambridge University Press:  20 November 2018

Ebad Mahmoodian
Ebad Mahmoodian*
Affiliation:
Community College of Philadelphia, Philadelphia, Pennsylvania
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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
Canadian Journal of Mathematics , Volume 29 , Issue 2 , 01 April 1977 , pp. 438 - 440
Copyright
Copyright © Canadian Mathematical Society 1977

References

1. Fulkerson, D. R., A. J. Hoffman and McAndrew, M. H., Some properties of graphs with multiple edges, Can. J. Math. 17 (1965), 166–177.Google Scholar
2. Tutte, W. T., A short proof of the factor theorem for finite graphs, Can. J. Math. 6 (1954), 347–352.Google Scholar
3. Tutte, W. T. Spanning subgraphs with specified valencies, Discrete Math. 9 (1974), 97–108.Google Scholar