Borg, Peter and Holroyd, Fred
(2009).

PDF (Not Set)
 Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (268Kb) 
DOI (Digital Object Identifier) Link:  https://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 rsets of G. For vV(G), let denote the star . G is said to be rEKR if there exists vV(G) such that for any nonstar family of pairwise intersecting sets in . If the inequality is strict, then G is strictly rEKR.
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 rEKR. 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 rEKR, 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 rEKR; 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:  0012365X 
Academic Unit/Department:  Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics Faculty of Science, Technology, Engineering and Mathematics (STEM) 
Item ID:  17514 
Depositing User:  Fred Holroyd 
Date Deposited:  06 Jul 2009 09:13 
Last Modified:  04 Oct 2016 22:26 
URI:  http://oro.open.ac.uk/id/eprint/17514 
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.