Title: Problems on Matchings and Independent Sets of a Graph,
Abstract: Let $G$ be a finite simple graph. For $X \subset V(G)$, the difference of
$X$, $d(X) := |X| - |N (X)|$ where $N(X)$ is the neighborhood of $X$ and $\max
\, \{d(X):X\subset V(G)\}$ is called the critical difference of $G$. $X$ is
called a critical set if $d(X)$ equals the critical difference and ker$(G)$ is
the intersection of all critical sets. It is known that ker$(G)$ is an
independent (vertex) set of $G$. diadem$(G)$ is the union of all critical
independent sets. An independent set $S$ is an inclusion minimal set with $d(S)
> 0$ if no proper subset of $S$ has positive difference.
A graph $G$ is called König-Egerváry if the sum of its independence
number ($\alpha (G)$) and matching number ($\mu (G)$) equals $|V(G)|$. It is
known that bipartite graphs are König-Egerváry.
In this paper, we study independent sets with positive difference for which
every proper subset has a smaller difference and prove a result conjectured by
Levit and Mandrescu in 2013. The conjecture states that for any graph, the
number of inclusion minimal sets $S$ with $d(S) > 0$ is at least the critical
difference of the graph. We also give a short proof of the inequality
$|$ker$(G)| + |$diadem$(G)| \le 2\alpha (G)$ (proved by Short in 2016).
A characterization of unicyclic non-König-Egerváry graphs is also
presented and a conjecture which states that for such a graph $G$, the critical
difference equals $\alpha (G) - \mu (G)$, is proved.
We also make an observation about ker$G)$ using Edmonds-Gallai Structure
Theorem as a concluding remark.