کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6423420 | 1342361 | 2013 | 12 صفحه PDF | دانلود رایگان |
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âXdegG(x)â¤c(F)â1; (2) c(F) is even and âxâXdegG(x)â¤c(F)+1; (3) G has no isolated vertices and âxâXdegG(x)â¤c(F)+|X|â2; or (4) G has no isolated vertices, c(F) is even and âxâXdegG(x)â¤c(F)+|X|â1. We show that the results in this paper are sharp in some sense.
Journal: Discrete Mathematics - Volume 313, Issue 13, 6 July 2013, Pages 1452-1463