Carl Feghali
Erdős–Ko–Rado theorems for a family of trees
Feghali, Carl; Johnson, Matthew; Thomas, Daniel
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 | Mar 29, 2024 |
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
Accepted Journal Article
(324 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright 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/
You might also like
Independent transversals versus transversals
(2019)
Conference Proceeding
Connected vertex cover for (sP1+P5)-free graphs
(2019)
Journal Article
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Finding a small number of colourful components
(2019)
Conference Proceeding
Clique-width for hereditary graph classes
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search