On some conjectures concerning critical independent sets of a graph

Abstract

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=\varnothing$). 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 Jarden, Levit, and Mandrescu.

arXiv comment10 pages, 3 figures