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.
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF (317Kb)
|Publisher Web site:||https://doi.org/10.1016/j.dam.2017.10.009|
|Publisher statement:||© 2018 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/|
|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|