Article ID Journal Published Year Pages File Type
4649889 Discrete Mathematics 2009 9 Pages PDF
Abstract

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 Γ″⊋Γ′Γ″⊋Γ′.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,