Abstract :
In this paper, we consider the relationship between f -factors and component-deleted subgraphs of graphs. Let G be a graph. A factor F of G is a complete-factor if every component of F is complete. If F is a complete-factor of G , and C is a component of F , then G − V ( C ) is a component-deleted subgraph. Let c ( G ) denote the number of components of G . Let f be an integer-valued function defined on V ( G ) with ∑ x ∈ V ( G ) f ( x ) even. Enomoto and Tokuda [H. Enomoto, T. Tokuda, Complete-factors and f -factors, Discrete Math. 220 (2000) 239–242] proved that if F is a complete-factor of G with c ( F ) ≥ 2 , and G − V ( C ) has an f -factor for each component C of F , then G has an f -factor. We extend their result, and show that it suffices to consider a complete-factor of G − X for some specified X ⊂ V ( G ) instead of G . Let F be a complete-factor of G − X with c ( F ) ≥ 2 . If G − V ( C ) has an f -factor for each component C of F , then G has an f -factor in each of the following cases: (1) ∑ x ∈ X deg G ( x ) ≤ c ( F ) − 1 ; (2) c ( F ) is even and ∑ x ∈ X deg G ( x ) ≤ c ( F ) + 1 ; (3) G has no isolated vertices and ∑ x ∈ X deg G ( x ) ≤ c ( F ) + | X | − 2 ; or (4) G has no isolated vertices, c ( F ) is even and ∑ x ∈ X deg G ( x ) ≤ c ( F ) + | X | − 1 . We show that the results in this paper are sharp in some sense.
