Graphs with the Erdos-Ko-Rado property
| 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 family of independent r-sets of V(G) by I^{(r)}(G). A graph G is said to be r-EKR if no intersecting subfamily of I^{(r)}(G) is larger than the largest such family all of whose members contain some fixed v \in V(G). If this inequality is always strict, then G is said to be strictly r-EKR. We show that if a graph G is r-EKR then its lexicographic product with any complete graph is r-EKR. For any graph G, we define μ(G) to be the minimum size of a maximal independent vertex set. We conjecture that, if 1 \leq r \leq 1/2μ(G), then G is r-EKR, and if r<1/2μ(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. | |
| dc.description | 15 pages, 2 figures, submitted to Discrete Mathematics (BCC19 issue) | |
| dc.identifier | https://arxiv.org/abs/math/0307073 | |
| dc.identifier | http://arxiv.org/abs/math/0307073 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/67986 | |
| dc.subject | Combinatorics | |
| dc.subject | 05D05; 05C35 | |
| dc.title | Graphs with the Erdos-Ko-Rado property | |
| dc.type | text |