Skip to main content

Research Repository

Advanced Search

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

Feghali, Carl; Johnson, Matthew; Thomas, Daniel

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


Authors

Carl Feghali

Daniel Thomas



Abstract

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.

Citation

Feghali, C., Johnson, M., & Thomas, D. (2018). Erdős–Ko–Rado theorems for a family of trees. Discrete Applied Mathematics, 236, 464-471. https://doi.org/10.1016/j.dam.2017.10.009

Journal Article Type Article
Acceptance Date Oct 17, 2017
Online Publication Date Feb 19, 2018
Publication Date Feb 19, 2018
Deposit Date Aug 2, 2018
Publicly Available Date Feb 19, 2019
Journal Discrete Applied Mathematics
Print ISSN 0166-218X
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 236
Pages 464-471
DOI https://doi.org/10.1016/j.dam.2017.10.009

Files





You might also like



Downloadable Citations