Compression and Erdos-Ko-Rado graphs

Details Compression and Erdos-Ko-Rado graphs Compression and Erdos-Ko-Rado graphs

2003-07-04

arxiv.org/abs/math/0307072v1

Mathematics

Combinatorics

9 pages, submitted to Discrete Mathematics (BCC19 issue)

Scientific paper

For a graph G and integer r\geq 1 we denote the collection of independent r-sets of G by I^{(r)}(G). If v\in V(G) then I_v^{(r)}(G) is the collection of all independent r-sets containing v. A graph G, is said to be r-EKR, for r\geq 1, iff no intersecting family A\subseteq I^{(r)}(G) is larger than max_{v\in V(G)}|I^{(r)}_v(G)|. There are various graphs which are known to have this property: the empty graph of order n\geq 2r (this is the celebrated Erdos-Ko-Rado theorem), any disjoint union of at least r copies of K_t for t\geq 2, and any cycle. In this paper we show how these results can be extended to other classes of graphs via a compression proof technique. In particular we show that any disjoint union of at least r complete graphs, each of order at least two, is r-EKR. We also show that paths are r-EKR for all r\geq 1.

Affiliated with

Also associated with

No associations

Rating

Compression and Erdos-Ko-Rado graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Compression and Erdos-Ko-Rado graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compression and Erdos-Ko-Rado graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-256555