Holroyd, Fred and Talbot, John
(2005).

PDF (Not Set)
 Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (222kB) 
DOI (Digital Object Identifier) Link:  https://doi.org/10.1016/j.disc.2004.08.028 

Google Scholar:  Look up in Google Scholar 
Abstract
For a graph G, vertex v of G and integer r >= 1, we denote the family of independent rsets of V(G) by I^(r)(G) and the subfamily by I^(r)_v(G); such a family is called a star. Then, G is said to be rEKR 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 rEKR. We show that if a graph is rEKR then its lexicographic product with any complete graph is rEKR.
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 rEKR, and if r < 1/2 mu(G), then G is strictly rEKR. 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 Item 

ISSN:  0012365X 
Extra Information:  Some of the symbols may not have transferred correctly into this bibliographic record and/or abstract. 
Keywords:  ErdosKoRado theorem; EKR property; graphs; independent vertex sets 
Academic Unit/School:  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:  02 May 2019 17:11 
URI:  http://oro.open.ac.uk/id/eprint/3524 
Share this page: 
Metrics
Altmetrics from Altmetric  Citations from Dimensions 
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.