Publication details for Professor Matthew JohnsonFeghali, Carl, Johnson, Matthew & Thomas, Daniel (2018). Erdős–Ko–Rado theorems for a family of trees. Discrete Applied Mathematics 236: 464-471.
- Publication type: Journal Article
- ISSN/ISBN: 0166-218X (print)
- DOI: 10.1016/j.dam.2017.10.009
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
A family of sets is intersecting if any two sets in the family intersect. Given a graph and an integer , let denote the family of independent sets of size of . For a vertex of , let denote the family of independent sets of size that contain . This family is called an -star and is its centre. Then is said to be -EKR if no intersecting subfamily of is bigger than the largest -star, and if every maximum size intersecting subfamily of is an -star, then is said to be strictly -EKR. Let denote the minimum size of a maximal independent set of . Holroyd and Talbot conjectured that if , then is -EKR, and it is strictly -EKR if .
This conjecture has been investigated for several graph classes, but not trees (except paths). In this note, we present a result for a family of trees. A depth-two claw is a tree in which every vertex other than the root has degree 1 or 2 and every vertex of degree 1 is at distance 2 from the root. We show that if is a depth-two claw, then is strictly -EKR if , confirming the conjecture of Holroyd and Talbot for this family.
Hurlbert and Kamat had conjectured that one can always find a largest -star of a tree whose centre is a leaf. Baber and Borg have independently shown this to be false. We show that, moreover, for all integers and , there exists a positive integer such that there is a tree where the centre of the largest -star is a vertex of degree at distance from every leaf.