کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6423420 1342361 2013 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
f-factors, complete-factors, and component-deleted subgraphs
ترجمه فارسی عنوان
فاکتورهای فاکتور، فاکتورهای کاملی و زیرگرافی های حذف شده کامپوننت
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 313, Issue 13, 6 July 2013, Pages 1452-1463
نویسندگان
,