On intersecting families of independent sets in trees

DOI10.1016/J.DAM.2022.06.028MaRDI QIDQ2172383zbMATH OpenOpenAlexFDO

Authors Vikram Kamat, Glenn H. Hurlbert

Publication date 15 September 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.08153

zbMATH Keywords

EKR graphindependent setintersecting familyspidertree

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Extremal set theory (05D05)

Abstract: A family of sets is intersecting if every pair of its sets intersect. A star is a family with some element (a center) in each of its sets. The classical 1961 result of ErdH{o}s, Ko, and Rado states that every intersecting family of r-sets with $rleqn/2$ has size at most that of a star. We say that graph G is r-EKR if, among all intersecting families of independent r-sets of G, the largest is attained by a star. In 2005 Holroyd and Talbot conjectured that every graph G is r-EKR for all $1leqrleqmu(G)/2$, where $mu(G)$ is the size of the smallest maximal independent set in G. We verified the conjecture in 2011 for all chordal graphs containing an isolated vertex. For graphs without isolated vertices it is difficult to determine the center of the largest star, which is often necessary to prove that they are EKR. A tree has the leaf property if its largest star occurs on one of its leaves. We proved that every tree T has the leaf property when $rleq4$, and in 2017 Borg and other authors gave examples of families of trees not having the leaf property when $rgeq5$. A split vertex in a tree is a vertex of degree at least 3. A spider is a tree with exactly one split vertex. Here we prove that all spiders have the leaf property for all $rleqalpha(G)$, where $alpha(G)$ is the independence number of $G$, and we characterize which of its leaves are maximum star centers. A pendant tree is one for which each of its split vertices is adjacent to a leaf. Here we show that all pendant trees have the leaf property for all $rleqalpha(G)$. We also consider pendant trees with exactly two split vertices and provide partial results on the locations of their maximum star centers.

Recommendations

• Erdös-Ko-Rado theorems for a family of trees
• Erdős-Ko-Rado theorems for chordal graphs and trees
• Very well-covered graphs with the Erdős-Ko-Rado property
• Stars on trees
• An Erdős-Ko-Rado theorem for unions of length 2 paths

Cites work

• A new short proof of the EKR theorem
• A proof and generalizations of the Erdős-Ko-Rado theorem using the method of linearly independent polynomials
• A simple proof of the Erdős-Chao Ko-Rado theorem
• An Erdős-Ko-Rado theorem for signed sets
• Compression and Erdős-Ko-Rado graphs
• Erdös-Ko-Rado theorems for a family of trees
• Erdös–Ko–Rado Theorem—22 Years Later
• Erdős-Ko-Rado from Kruskal-Katona
• Erdős-Ko-Rado theorems for chordal graphs and trees
• Erdős-Ko-Rado theorems. Algebraic approaches
• Extremal t -intersecting sub-families of hereditary families
• Graphs with the Erdős-Ko-Rado property
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3461973 (Why is no real title available?)
• scientific article; zbMATH DE number 3477225 (Why is no real title available?)
• scientific article; zbMATH DE number 3489128 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• INTERSECTING FAMILIES OF SEPARATED SETS
• Intersection theorems for systems of finite sets
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• New injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
• On stars in caterpillars and lobsters
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Stars on trees
• The Erdős-Ko-Rado properties of various graphs containing singletons

Cited in

(6)

• Erdös-Ko-Rado theorems for a family of trees
• On stars in caterpillars and lobsters
• A Note on Independent Sets in Trees
• On generalized independent subsets of trees
• On the Holroyd-Talbot conjecture for sparse graphs
• On the star of the family of independent sets in a graph

This page was built for publication: On intersecting families of independent sets in trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2172383)