Graphs with the Erdős-Ko-Rado property
From MaRDI portal
Abstract: For a graph G and integer r geq 1 we denote the family of independent r-sets of V(G) by I^{(r)}(G). A graph G is said to be r-EKR if no intersecting subfamily of I^{(r)}(G) is larger than the largest such family all of whose members contain some fixed v in V(G). If this inequality is always strict, then G is said to be strictly r-EKR. We show that if a graph G is r-EKR then its lexicographic product with any complete graph is r-EKR. For any graph G, we define mu(G) to be the minimum size of a maximal independent vertex set. We conjecture that, if 1 leq r leq 1/2mu(G), then G is r-EKR, and if r<1/2mu(G), then G is strictly r-EKR. This is known to be true when G is an empty graph, a cycle, a path or the disjoint union of complete graphs. We show that it is also true when G is the disjoint union of a pair of complete multipartite graphs.
Recommendations
Cites work
- scientific article; zbMATH DE number 3652388 (Why is no real title available?)
- scientific article; zbMATH DE number 3641492 (Why is no real title available?)
- 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 Theorem—22 Years Later
- Erdős-Ko-Rado and Hilton-Milner type theorems for intersecting chains in posets
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Some covering concepts in graphs
Cited in
(46)- Cross-intersecting subfamilies of levels of hereditary families
- The maximum sum of sizes of cross-intersecting families of subsets of a set
- The Erdős-Ko-Rado theorem for twisted Grassmann graphs
- An Erdős-Ko-Rado theorem for permutations with fixed number of cycles
- On the star of the family of independent sets in a graph
- Erdös-Ko-Rado theorem for ladder graphs
- Erdős regular graphs of even degree
- An Erdős-Ko-Rado theorem for unions of length 2 paths
- The EKR property for flag pure simplicial complexes without boundary
- The covering lemma and q-analogues of extremal set theory problems
- A cross‐intersection theorem for subsets of a set
- The Erdős-Ko-Rado properties of various graphs containing singletons
- The Erdős-Ko-Rado properties of set systems defined by double partitions
- Compression and Erdős-Ko-Rado graphs
- On stars in caterpillars and lobsters
- Very well-covered graphs with the Erdős-Ko-Rado property
- Erdős-Ko-Rado theorems for chordal graphs and trees
- Erdős-Ko-Rado theorems for simplicial complexes
- Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas
- Cross-intersecting non-empty uniform subfamilies of hereditary families
- Strongly intersecting integer partitions
- Graphs with the balas—uhry property
- An analogue of the Erdős-Ko-Rado theorem for weak compositions
- The EKR-module property of pseudo-Paley graphs of square order
- Non-trivial intersecting uniform sub-families of hereditary families
- Erdös-Ko-Rado theorems for a family of trees
- On Chvàtal's conjecture and a conjecture on families of signed sets
- The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem
- On the Holroyd-Talbot conjecture for sparse graphs
- A non-trivial intersection theorem for permutations with fixed number of cycles
- Restricted intersecting families on simplicial complex
- A Hilton-Milner-type theorem and an intersection conjecture for signed sets
- A Deza-Frankl type theorem for set partitions
- On intersecting families of independent sets in trees
- A generalization of the Erdős-Ko-Rado theorem
- Maximum hitting of a set by compressed intersecting families
- The maximum product of sizes of cross-intersecting families
- Graphs with no induced house nor induced hole have the de Bruijn–Erdös property
- A sharp bound for the product of weights of cross-intersecting families
- Erdös-Pósa Property of Obstructions to Interval Graphs
- Stars on trees
- The maximum product of weights of cross-intersecting families
- Erdős-Ko-Rado type theorems for simplicial complexes
- On \(t\)-intersecting families of signed sets and permutations
- The number of \(s\)-separated \(k\)-sets in various circles
- On \(k\)-wise \(L\)-intersecting families for simplicial complexes
This page was built for publication: Graphs with the Erdős-Ko-Rado property
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1779495)
