Graphs with the Erdős-Ko-Rado property (Q1779495): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 05:38, 5 March 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