Graphs with the Erdős-Ko-Rado property (Q1779495): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: F. C. Holroyd / rank | |||
Property / author | |||
Property / author: F. C. Holroyd / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2083241416 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: math/0307073 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An Erdős-Ko-Rado theorem for signed sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Erdös–Ko–Rado Theorem—22 Years Later / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Erdős-Ko-Rado and Hilton-Milner type theorems for intersecting chains in posets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Compression and Erdős-Ko-Rado graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A simple proof of the Erdős-Chao Ko-Rado theorem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some covering concepts in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4200104 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3852228 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 12:00, 10 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Graphs with the Erdős-Ko-Rado property |
scientific article |
Statements
Graphs with the Erdős-Ko-Rado property (English)
0 references
1 June 2005
0 references
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.
0 references
EKR property
0 references
independent vertex set
0 references