Factors and vertex-deleted subgraphs

AbstractA relationship is considered between an f-factor of a graph and that of its vertex-deleted subgraphs. Katerinis [Some results on the existence of 2n-factors in terms of vertex-deleted subgraphs, Ars Combin. 16 (1983) 271–277] proved that for even integer k, if G-x has a k-factor for each x∈V(G), then G has a k-factor. Enomoto and Tokuda [Complete-factors and f-factors, Discrete Math. 220 (2000) 239–242] generalized Katerinis’ result to f-factors, and proved that if G-x has an f-factor for each x∈V(G), then G has an f-factor for an integer-valued function f defined on V(G) with ∑x∈V(G)f(x) even. In this paper, we consider a similar problem to that of Enomoto and Tokuda, where for several vertices x we do not have to know whether G-x has an f-factor. Let G be a graph, X be a set of vertices, and let f be an integer-valued function defined on V(G) with ∑x∈V(G)f(x) even, |V(G)-X|⩾2. We prove that if ∑x∈XdegG(x)⩽2|V(G)-X|-1 and if G-x has an f-factor for each x∈V(G)-X, then G has an f-factor. Moreover, if G excludes an isolated vertex, then we can replace the condition ∑x∈XdegG(x)≤2|V(G)-X|-1 with ∑x∈XdegG(x)⩽2|V(G)-X|+|X|-3. Furthermore the condition will be ∑x∈XdegG(x)⩽2|V(G)-X|-1 when |X|=1