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.
This paper deals with the following, rather general problem. Let \(G\) be a graph, \({\mathcal I}^{(r)}(G)\) denote its \(r\)-element independent sets, while \({\mathcal I}^{(r)}_v(G)\) denote those \(r\)-element independent sets which contain vertex \(v.\) A graph is called \(r\)-EKR if there is no bigger intersecting subfamily in \({\mathcal I}^{(r)}(G)\) than the maximum size \(| {\mathcal I}^{(r)}_v(G)| .\) The main question is to describe the \(r\)-EKR graphs. If \(G\) is an empty graph with \(n\) vertices, then to determine the biggest \(r\) such that \(G\) is \(r\)-EKR is the well-known Erdős-Ko-Rado problem. This paper's main result is: if \(G\) is \(r\)-EKR, then its lexicographic product with any complete graph is also \(r\)-EKR.
Recommendations
Cites work
- 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
- scientific article; zbMATH DE number 3652388 (Why is no real title available?)
- scientific article; zbMATH DE number 3641492 (Why is no real title available?)
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Some covering concepts in graphs
Cited in
(48)- On t-intersecting families of signed sets and permutations
- The Erdős-Ko-Rado properties of various graphs containing singletons
- The Erdős-Ko-Rado properties of set systems defined by double partitions
- A generalization of the Erdős-Ko-Rado theorem
- Erdös-Ko-Rado theorems for a family of trees
- Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas
- Compression and Erdős-Ko-Rado graphs
- An Erdős-Ko-Rado theorem for unions of length 2 paths
- On stars in caterpillars and lobsters
- The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem
- The EKR-module property of pseudo-Paley graphs of square order
- The maximum sum of sizes of cross-intersecting families of subsets of a set
- On intersecting families of independent sets in trees
- Cross-intersecting subfamilies of levels of hereditary families
- Restricted intersecting families on simplicial complex
- The EKR property for flag pure simplicial complexes without boundary
- A Deza-Frankl type theorem for set partitions
- The maximum product of sizes of cross-intersecting families
- Erdős-Ko-Rado type theorems for simplicial complexes
- Cross-intersecting non-empty uniform subfamilies of hereditary families
- Erdős-Ko-Rado theorems for chordal graphs and trees
- Erdős-Ko-Rado theorems for simplicial complexes
- The Erdős-Ko-Rado theorem for twisted Grassmann graphs
- The maximum product of weights of cross-intersecting families
- Erdös-Pósa Property of Obstructions to Interval Graphs
- Non-trivial intersecting uniform sub-families of hereditary families
- A Hilton-Milner-type theorem and an intersection conjecture for signed sets
- An analogue of the Erdős-Ko-Rado theorem for weak compositions
- An Erdős-Ko-Rado theorem for permutations with fixed number of cycles
- Graphs with the balas—uhry property
- Erdös-Ko-Rado theorem for ladder graphs
- The number of s-separated k-sets in various circles
- A sharp bound for the product of weights of cross-intersecting families
- Stars on trees
- A cross‐intersection theorem for subsets of a set
- Erdős regular graphs of even degree
- On the Holroyd-Talbot conjecture for sparse graphs
- On Chvàtal's conjecture and a conjecture on families of signed sets
- Graphs with no induced house nor induced hole have the de Bruijn–Erdös property
- The covering lemma and q-analogues of extremal set theory problems
- Very well-covered graphs with the Erdős-Ko-Rado property
- On the star of the family of independent sets in a graph
- On \(k\)-wise \(L\)-intersecting families for simplicial complexes
- Maximum hitting of a set by compressed intersecting families
- Strict Erdős-Ko-Rado for simplicial complexes (extended abstract)
- An EKR theorem for a class of generalized Hamming graphs
- Strongly intersecting integer partitions
- A non-trivial intersection theorem for permutations with fixed number of cycles
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)
