کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649713 1342464 2008 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The Ramsey numbers for disjoint unions of graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The Ramsey numbers for disjoint unions of graphs
چکیده انگلیسی

For given graphs GG and H,H, the Ramsey number R(G,H)R(G,H) is the smallest natural number nn such that for every graph FF of order nn: either FF contains GG or the complement of FF contains H.H. In this paper we investigate the Ramsey number of a disjoint union of graphs R(⋃i=1kGi,H). For any natural integer k  , we contain a general upper bound, R(kG,H)⩽R(G,H)+(k-1)|V(G)|R(kG,H)⩽R(G,H)+(k-1)|V(G)|. We also show that if m=2n-4m=2n-4, 2n-82n-8 or 2n-62n-6, then R(kSn,Wm)=R(Sn,Wm)+(k-1)nR(kSn,Wm)=R(Sn,Wm)+(k-1)n. Furthermore, if |Gi|>(|Gi|-|Gi+1|)(χ(H)-1)|Gi|>(|Gi|-|Gi+1|)(χ(H)-1) and R(Gi,H)=(χ(H)-1)(|Gi|-1)+1R(Gi,H)=(χ(H)-1)(|Gi|-1)+1, for each ii, then R(⋃i=1kGi,H)=R(Gk,H)+∑i=1k-1|Gi|.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 10, 28 May 2008, Pages 2046–2049
نویسندگان
, , ,