Inequalities Involving Core, Corona, and Critical Sets in General Graphs

Let $\alpha (G)$ denote the cardinality of a maximum independent set. An independent set $I$ of $G$ is critical if $\mid I\mid -\mid N(I)\mid \ge \mid J\mid -\mid N(J)\mid$ for every independent set $J$ of $G$. Let $\text{core}(G)$ and $\text{corona}(G)$ be the intersection/union of all maximum independent sets of $G$. Let $\text{ker}(G)$ and $\text{diadem}(G)$ be the intersection/union of all critical independent sets of $G$. In this paper we prove that $$\mid \text{corona}(G)\mid +\mid \text{core}(G)\mid \le 2\alpha (G)+k,$$ \noindent where $k$ is the number of vertex-distinct odd cycles in $G$, thus confirming a recent conjecture in the area. Moreover, we prove that $$\mid \text{nucleus}(G)\mid +\mid \text{diadem}(G)\mid \le 2\alpha (G),$$ \noindent thereby confirming another conjecture (Levit–Mandrescu 2014). As an application of these facts, we obtain a chain of inequalities $$\mid \text{nucleus}(G)\mid +\mid \text{diadem}(G)\mid \le 2\alpha (G)\le \mid \text{corona}(G)\mid +\mid \text{core}(G)\mid \le 2\alpha (G)+k\mathrm{.}$$ \noindent The paper concludes with a collection of related open problems.