The Open UniversitySkip to content
 

The Erdős-Ko-Rado properties of various graphs containing singletons

Borg, Peter and Holroyd, Fred (2009). The Erdős-Ko-Rado properties of various graphs containing singletons. Discrete Mathematics, 309(9) pp. 2877–2885.

Full text available as:
[img]
Preview
PDF (Not Set) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (268Kb)
DOI (Digital Object Identifier) Link: http://dx.doi.org/10.1016/j.disc.2008.07.021
Google Scholar: Look up in Google Scholar

Abstract

Let G=(V,E) be a graph. For r≥1, let be the family of independent vertex r-sets of G. For vV(G), let denote the star . G is said to be r-EKR if there exists vV(G) such that for any non-star family of pair-wise intersecting sets in . If the inequality is strict, then G is strictly r-EKR.

Let Γ be the family of graphs that are disjoint unions of complete graphs, paths, cycles, including at least one singleton. Holroyd, Spencer and Talbot proved that, if GΓ and 2r is no larger than the number of connected components of G, then G is r-EKR. However, Holroyd and Talbot conjectured that, if G is any graph and 2r is no larger than μ(G), the size of a smallest maximal independent vertex set of G, then G is r-EKR, and strictly so if 2r<μ(G). We show that in fact, if GΓ and 2r is no larger than the independence number of G, then G is r-EKR; we do this by proving the result for all graphs that are in a suitable larger set Γ′Γ. We also confirm the conjecture for graphs in an even larger set Γ″Γ′.

Item Type: Journal Article
Copyright Holders: 2008 Elsevier B.V.
ISSN: 0012-365X
Academic Unit/Department: Mathematics, Computing and Technology > Mathematics and Statistics
Item ID: 17514
Depositing User: Fred Holroyd
Date Deposited: 06 Jul 2009 09:13
Last Modified: 25 Oct 2012 04:32
URI: http://oro.open.ac.uk/id/eprint/17514
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