Compression and Erdos-Ko-Rado graphs
| dc.creator | Holroyd, Fred | |
| dc.creator | Talbot, John | |
| dc.date | 2003-07-04 | |
| dc.date.accessioned | 2026-07-07T04:59:26Z | |
| dc.date.available | 2026-07-07T04:59:26Z | |
| dc.description | 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. | |
| dc.description | 9 pages, submitted to Discrete Mathematics (BCC19 issue) | |
| dc.identifier | https://arxiv.org/abs/math/0307072 | |
| dc.identifier | http://arxiv.org/abs/math/0307072 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/67985 | |
| dc.subject | Combinatorics | |
| dc.subject | 05D05; 05C35 | |
| dc.title | Compression and Erdos-Ko-Rado graphs | |
| dc.type | text |