کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420828 683987 2006 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Path-fan Ramsey numbers
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Path-fan Ramsey numbers
چکیده انگلیسی

For two given graphs FF and HH, the Ramsey number R(F,H)R(F,H) is the smallest positive integer pp such that for every graph GG on pp vertices the following holds: either GG contains FF as a subgraph or the complement of GG contains HH as a subgraph. In this paper, we study the Ramsey numbers R(Pn,Fm)R(Pn,Fm), where PnPn is a path on nn vertices and FmFm is the graph obtained from mm disjoint triangles by identifying precisely one vertex of every triangle (FmFm is the join of K1K1 and mK2mK2). We determine the exact values of R(Pn,Fm)R(Pn,Fm) for the following values of nn and mm: 1⩽n⩽51⩽n⩽5 and m⩾2m⩾2; n⩾6n⩾6 and 2⩽m⩽(n+1)/22⩽m⩽(n+1)/2; 6⩽n⩽76⩽n⩽7 and m⩾n-1m⩾n-1; n⩾8n⩾8 and n-1⩽m⩽nn-1⩽m⩽n or ((q·n-2q+1)/2⩽m⩽(q·n-q+2)/2((q·n-2q+1)/2⩽m⩽(q·n-q+2)/2 with 3⩽q⩽n-5)3⩽q⩽n-5) or m⩾(n-3)2/2m⩾(n-3)2/2; odd n⩾9n⩾9 and ((q·n-3q+1)/2⩽m⩽(q·n-2q)/2((q·n-3q+1)/2⩽m⩽(q·n-2q)/2 with 3⩽q⩽(n-3)/2)3⩽q⩽(n-3)/2) or ((q·n-q-n+4)/2⩽m⩽(q·n-2q)/2((q·n-q-n+4)/2⩽m⩽(q·n-2q)/2 with (n-1)/2⩽q⩽n-5)(n-1)/2⩽q⩽n-5). Moreover, we give nontrivial lower bounds and upper bounds for R(Pn,Fm)R(Pn,Fm) for the other values of mm and nn.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 154, Issue 9, 1 June 2006, Pages 1429–1436
نویسندگان
, ,