2003/07/04 by Fred Holroyd, Holroyd, Fred, John Talbot +1
Computer Science · Mathematics · #05C35 #05D05 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05C35 #msc:05D05
paper · pdf · doi:10.48550/arxiv.math/0307073
15 pages, 2 figures, submitted to Discrete Mathematics (BCC19 issue)
arxiv created 2003/07/04 · openalex publication_date 2003/07/04 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G and integer r ≥ 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 ∈ 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 ≤ r ≤ 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.