کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649302 1342449 2006 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Factors and vertex-deleted subgraphs
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Factors and vertex-deleted subgraphs
چکیده انگلیسی

A relationship is considered between an f  -factor of a graph and that of its vertex-deleted subgraphs. Katerinis [Some results on the existence of 2n2n-factors in terms of vertex-deleted subgraphs, Ars Combin. 16 (1983) 271–277] proved that for even integer k  , if G-xG-x has a k  -factor for each x∈V(G)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-xG-x has an f  -factor for each x∈V(G)x∈V(G), then G has an f-factor for an integer-valued function f   defined on V(G)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-xG-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)V(G) with ∑x∈V(G)f(x) even, |V(G)-X|⩾2|V(G)-X|⩾2. We prove that if ∑x∈XdegG(x)⩽2|V(G)-X|-1 and if G-xG-x has an f  -factor for each x∈V(G)-Xx∈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|X|=1.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issue 6, 6 April 2006, Pages 607–611
نویسندگان
,