Graphs with the Erdős-Ko-Rado property (Q1779495): Difference between revisions

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.