2018/11/12 by Carl Feghali, Feghali, Carl
Computer Science · Mathematics · #05D05 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1811.04902
openalex publication_date 2018/11/12 · openalex created_date 2018/11/16 · openalex updated_date 2026/07/28
A family of sets is intersecting if any two sets in the family intersect. Given a graph G and an integer r≥ 1, let I(r)(G) denote the family of independent sets of size r of G. For a vertex v of G, let I(r)v(G) denote the family of independent sets of size r that contain v. This family is called an r-star. Then G is said to be r-EKR if no intersecting subfamily of I(r)(G) is bigger than the largest r-star. Let k, n, r ≥ 1, and let T(n, k) be the tree of depth two in which the root has degree n and every neighbour of the root has the same number k + 1 of neighbours. For each k ≥ 2, we show that T(n, k) is r-EKR if 2r ≤ n, extending results of Borg and of Feghali, Johnson and Thomas who considered the case k = 1.