An extension of Tutte's 1-factor theorem |
| |
Authors: | Michel Las Vergnas |
| |
Institution: | C.N.R.S., Université Pièrre et Marie Curie, U.E.R. 48, 4 place Jussieu, 75230 Paris, France |
| |
Abstract: | We prove the following theorem: Let G be a graph with vertex-set V and ?, g be two integer-valued functions defined on V such that for all x ∈ V. Then G contains a factor F such that for all x ∈ V if and only if for every subset X of V, is at least equal to the number of connected components C of GV ? X] such that either C = {x} and g(x) = 1, or |C| is odd ?3 and for all x ∈ C. Applications are given to certain combinatorial geometries associated with factors of graphs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|