The Erdős-Ko-Rado properties of various graphs containing singletons (Q1043643)

Let \(G=(V,E)\) be a graph. For \(r\geq 1\), let \({\mathcal T}^{(r)}_G\) be the family of independent vertex \(r\)-sets of \(G\). For \(v\in V(G)\), let \({\mathcal T}^{(r)}_G(v)\) denote the star \(\{A\in{\mathcal I}^{(r)}_G: v\in A\}\). \(G\) is said to be \(r\)-EKR if there exists \(v\in V(G)\) such that \(|{\mathcal A}|\leq |{\mathcal T}^{(r)}_G(v)|\) for any non-star family \(\mathcal A\) of pair-wise intersecting sets in \({\mathcal T}^{(r)}_G\). If the inequality is strict, then \(G\) is strictly \(r\)-EKR. Let \(\Gamma\) be the family of graphs that are disjoint unions of complete graphs, paths, cycles, including at least one singleton. \textit{F. Holroyd}, \textit{C. Spencer}, and \textit{J. Talbot} [Discrete Math. 293, No. 1-3, 155--164 (2005; Zbl 1064.05141)] proved that, if \(G\in\Gamma\) and \(2r\) is no larger than the number of connected components of \(G\), then \(G\) is \(r\)-EKR. However, Holroyd and Talbot conjectured that, if \(G\) is any graph and \(2r\) is no larger than \(\mu(G)\), the size of a smallest maximal independent vertex set of \(G\), then \(G\) is \(r\)-EKR, and strictly so if \(2r<\mu(G)\). We show that in fact, if \(G\in\Gamma\) and \(2r\) is no larger than the independence number of \(G\), then \(G\) is \(r\)-EKR; we do this by proving the result for all graphs that are in a suitable larger set \(\Gamma'\supseteq\Gamma\). We also confirm the conjecture for graphs in an even larger set \(\Gamma''\supseteq\Gamma'\).