2003/07/04 by Fred Holroyd, Holroyd, Fred, John Talbot +1 · 2 citations
Mathematics · #05C35 #05D05 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C35 #msc:05D05
paper · pdf · doi:10.48550/arxiv.math/0307072
9 pages, submitted to Discrete Mathematics (BCC19 issue)
arxiv created 2003/07/04 · arxiv updated 2009/11/30
For a graph G and integer r≥ 1 we denote the collection of independent r-sets of G by I(r)(G). If v∈ V(G) then Iv(r)(G) is the collection of all independent r-sets containing v. A graph G, is said to be r-EKR, for r≥ 1, iff no intersecting family A⊆ I(r)(G) is larger than maxv∈ V(G)|I(r)v(G)|. There are various graphs which are known to have this property: the empty graph of order n≥ 2r (this is the celebrated Erdos-Ko-Rado theorem), any disjoint union of at least r copies of Kt for t≥ 2, and any cycle. In this paper we show how these results can be extended to other classes of graphs via a compression proof technique. In particular we show that any disjoint union of at least r complete graphs, each of order at least two, is r-EKR. We also show that paths are r-EKR for all r≥ 1.