The Open UniversitySkip to content

Compression and Erdos-Ko-Rado graphs

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:
PDF (Not Set) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (124Kb)
DOI (Digital Object Identifier) Link:
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_{v in V(G)} |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
ISSN: 0012-365X
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: Mathematics, Computing and Technology > Mathematics and Statistics
Mathematics, Computing and Technology
Item ID: 3505
Depositing User: Fred Holroyd
Date Deposited: 27 Jun 2006
Last Modified: 16 Jan 2016 00:38
Share this page:


Scopus Citations

Actions (login may be required)

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340