We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Erdős–Ko–Rado theorems for a family of trees.

Feghali, Carl and Johnson, Matthew and Thomas, Daniel (2018) 'Erdős–Ko–Rado theorems for a family of trees.', Discrete applied mathematics., 236 . pp. 464-471.


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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
Publisher Web site:
Publisher statement:© 2018 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Date accepted:17 October 2017
Date deposited:03 August 2018
Date of first online publication:19 February 2018
Date first made open access:19 February 2019

Save or Share this output

Look up in GoogleScholar