On Factors of a Graph
Canadian journal of mathematics, Tome 29 (1977) no. 2, pp. 438-440
Voir la notice de l'article provenant de la source Cambridge University Press
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.
Mahmoodian, Ebad. On Factors of a Graph. Canadian journal of mathematics, Tome 29 (1977) no. 2, pp. 438-440. doi: 10.4153/CJM-1977-046-7
@article{10_4153_CJM_1977_046_7,
author = {Mahmoodian, Ebad},
title = {On {Factors} of a {Graph}},
journal = {Canadian journal of mathematics},
pages = {438--440},
year = {1977},
volume = {29},
number = {2},
doi = {10.4153/CJM-1977-046-7},
url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1977-046-7/}
}
[1] 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] 2. Tutte, W. T., A short proof of the factor theorem for finite graphs, Can. J. Math. 6 (1954), 347–352. Google Scholar
[3] 3. Tutte, W. T. Spanning subgraphs with specified valencies, Discrete Math. 9 (1974), 97–108. Google Scholar
Cité par Sources :