2015/06/25 by Carl Feghali, Matthew Johnson, Feghali, Carl +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph Theory and Algorithms #Graph theory and applications #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1506.07741
Added new section on "Centres of Largest $r$-stars in Trees"
openalex publication_date 2015/06/25 · arxiv created 2016/04/13 · arxiv updated 2016/04/14 · openalex created_date 2019/07/30 · openalex updated_date 2026/07/28
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 and v is the centre of the star. Then G is said to be r-EKR if no pairwise intersecting subfamily of I(r)(G) is bigger than the largest r-star, and if every maximum size pairwise intersecting subfamily of I(r)(G) is an r-star, then G is said to be strictly r-EKR. Let μ(G) denote the minimum size of a maximal independent set of G. Holroyd and Talbot conjectured that if 2r ≤ μ(G), then G is r-EKR and strictly r-EKR if 2r < μ(G). An elongated claw is a tree in which one vertex is designated the root and no vertex other than the root has degree greater than 2. A depth-two claw is an elongated claw in which every vertex of degree~1 is at distance 2 from the root. We show that if G is a depth-two claw, then G is strictly r-EKR if 2r ≤ μ(G)+1, confirming the conjecture of Holroyd and Talbot for this family. We also show that if G is an elongated claw with n leaves and at least one leaf adjacent to the root, then G is r-EKR if 2r ≤ n. Hurlbert and Kamat had conjectured that one can always find a largest r-star of a tree whose centre is a leaf. Baber and Borg have separately shown this to be false. We show that, moreover, for all n ≥ 2, d ≥ 3, there exists a positive integer r such that there is a tree where the centre of the largest r-star is a vertex of degree n at distance at least d from every leaf.