The Open UniversitySkip to content

Graphs with the Erdos-Ko-Rado property

Holroyd, Fred and Talbot, John (2005). Graphs with the Erdos-Ko-Rado property. Discrete Mathematics, 293(1-3) pp. 165–176.

Full text available as:
PDF (Not Set) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (217Kb)
DOI (Digital Object Identifier) Link:
Google Scholar: Look up in Google Scholar


For a graph G, vertex v of G and integer r >= 1, we denote the family of independent r-sets of V(G) by I^(r)(G) and the subfamily {A in I^(r)(G): v in A} by I^(r)_v(G); such a family is called a star. Then, G is said to be r-EKR if no intersecting subfamily of I^(r)(G) is larger than the largest star in I^(r)(G). If every intersecting subfamily of I^(r)_v(G) of maximum size is a star, then G is said to be strictly r-EKR. We show that if a graph is r-EKR then its lexicographic product with any complete graph is r-EKR.
For any graph G, we define mu(G) to be the minimum size of a maximal independent vertex set. We conjecture that, if 1 <= r <= 1/2 mu(G), then G is r-EKR, and if r < 1/2 mu(G), then G is strictly r-EKR. This is known to be true when G is an empty graph, a cycle, a path or the disjoint union of complete graphs. We show that it is also true when G is the disjoint union of a pair of complete multipartite graphs.

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: Erdos-Ko-Rado theorem; EKR property; graphs; independent vertex sets
Academic Unit/Department: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 3524
Depositing User: Fred Holroyd
Date Deposited: 27 Jun 2006
Last Modified: 04 Oct 2016 12:56
Share this page:


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