کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649889 1342468 2009 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The Erdős-Ko-Rado properties of various graphs containing singletons
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The Erdős-Ko-Rado properties of various graphs containing singletons
چکیده انگلیسی

Let G=(V,E)G=(V,E) be a graph. For r≥1r≥1, let IG(r) be the family of independent vertex rr-sets of GG. For v∈V(G)v∈V(G), let IG(r)(v) denote the star  {A∈IG(r):v∈A}. GG is said to be r-EKR   if there exists v∈V(G)v∈V(G) such that |A|≤|IG(r)(v)| for any non-star family AA of pair-wise intersecting sets in IG(r). If the inequality is strict, then GG is strictly  rr-EKR.Let ΓΓ be the family of graphs that are disjoint unions of complete graphs, paths, cycles, including at least one singleton. Holroyd, Spencer and Talbot proved that, if G∈ΓG∈Γ and 2r2r is no larger than the number of connected components of GG, then GG is rr-EKR. However, Holroyd and Talbot conjectured that, if GG is any graph and 2r2r is no larger than μ(G)μ(G), the size of a smallest maximal independent vertex set of GG, then GG is rr-EKR, and strictly so if 2r<μ(G)2r<μ(G). We show that in fact, if G∈ΓG∈Γ and 2r2r is no larger than the independence number of GG, then GG is rr-EKR; we do this by proving the result for all graphs that are in a suitable larger set Γ′⊋ΓΓ′⊋Γ. We also confirm the conjecture for graphs in an even larger set Γ″⊋Γ′Γ″⊋Γ′.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 9, 6 May 2009, Pages 2877–2885
نویسندگان
, ,