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: https://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: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 3505
Depositing User: Fred Holroyd
Date Deposited: 27 Jun 2006
Last Modified: 07 Oct 2016 00:34
URI: http://oro.open.ac.uk/id/eprint/3505
Share this page:

Altmetrics

Scopus Citations

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.

▼ Automated document suggestions from open access sources

Actions (login may be required)

Policies | Disclaimer

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