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:
[img]
Preview
PDF (Not Set) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (124Kb)
URL: http://www.elsevier.com/wps/find/journaldescriptio...
DOI (Digital Object Identifier) Link: http://dx.doi.org/10.1016/j.disc.2004.08.041
Google Scholar: 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_{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
Item ID: 3505
Depositing User: Fred Holroyd
Date Deposited: 27 Jun 2006
Last Modified: 06 Dec 2010 17:38
URI: http://oro.open.ac.uk/id/eprint/3505
Share this page:

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340   general-enquiries@open.ac.uk