On some conjectures concerning critical independent sets of a graph (Q2629485): Difference between revisions

Summary: Let \(G\) be a simple graph with vertex set \(V(G)\). A set \(S\subseteq V(G)\) is independent if no two vertices from \(S\) are adjacent. For \(X\subseteq V(G)\), the difference of \(X\) is \(d(X) = |X|-|N(X)|\) and an independent set \(A\) is critical if \(d(A) = \max \{d(X): X\subseteq V(G)\text{ is an independent set}\}\) (possibly \(A=\emptyset\)). Let \(\text{nucleus}(G)\) and \(\text{diadem}(G)\) be the intersection and union, respectively, of all maximum size critical independent sets in \(G\). In this paper, we will give two new characterizations of König-Egerváry graphs involving \(\text{nucleus}(G)\) and \(\text{diadem}(G)\). We also prove a related lower bound for the independence number of a graph. This work answers several conjectures posed by \textit{A. Jarden}, \textit{V. E. Levit} and \textit{E. Mandrescu} [``Critical and maximum independent sets of a graph'', Preprint, \url{arXiv:1506.00255}].