Holroyd, Fred; Spencer, Claire and Talbot, John (2005). Compression and Erdos-Ko-Rado graphs. Discrete Mathematics, 293(1-3) pp. 155–164.

Full text available as:  Preview
PDF (Not Set) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
URL: http://www.elsevier.com/wps/find/journaldescriptio... https://doi.org/10.1016/j.disc.2004.08.041 Look up in Google Scholar

## Abstract

For a graph G and integer r >= 1 we denote the collection of independent r-setsof G by I^(r)(G). If v is in V(G) then I^(r)_v(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 of I^(r)(G) is larger than max_ |I^(r)_v(G)|. There are various graphs that 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 atleast r copies of K_t 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 extend a theorem of Berge, showing 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.

Item Type: Journal Item 0012-365X Some of the symbols may not have transferred correctly into this bibliographic record and/or abstract.--- Extremal combinatorics; set systems; intersection problems Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and StatisticsFaculty of Science, Technology, Engineering and Mathematics (STEM) 3505 Fred Holroyd 27 Jun 2006 03 May 2019 13:26 http://oro.open.ac.uk/id/eprint/3505    