Holroyd, Fred; Spencer, Claire and Talbot, John
PDF (Not Set)
- Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
|DOI (Digital Object Identifier) Link:||http://doi.org/10.1016/j.disc.2004.08.041|
|Google Scholar:||Look up in Google Scholar|
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 Article|
|Extra Information:||Some of the symbols may not have transferred correctly into this bibliographic record and/or abstract.---|
|Keywords:||Extremal combinatorics; set systems; intersection problems|
|Academic Unit/Department:||Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
|Depositing User:||Fred Holroyd|
|Date Deposited:||27 Jun 2006|
|Last Modified:||04 Aug 2016 01:51|
|Share this page:|
Download history for this item
These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.