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:

Preview

PDF (Not Set) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (217Kb)

DOI (Digital Object Identifier) Link:	http://dx.doi.org/doi: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 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:	Mathematics, Computing and Technology > Mathematics and Statistics
Item ID:	3524
Depositing User:	Fred Holroyd
Date Deposited:	27 Jun 2006
Last Modified:	04 Dec 2010 06:19
URI:	http://oro.open.ac.uk/id/eprint/3524

Actions (login may be required)

	View Item
	Public: Report issue / request change

Policies | Disclaimer