Vertices Belonging to All Critical Sets of a Graph
Vadim E. Levit, Eugen Mândrescu · SIAM Journal on Discrete Mathematics · 2012
Let $G=(V,E)$ be a graph. A set $S\subseteq V$ is independent if no two vertices from S are adjacent, while $\mathrm{core}(G)$ is the intersection of all maximum independent sets [V. E. Levit and E. Mandrescu, Discrete Appl. Math., 117 (2002), pp. 149–161]. The independence number $\alpha(G)$ is the cardinality of a largest independent set, and $\mu(G)$ is the size of a maximum matching of G. The neighborhood of $A\subseteq V$ is $\mathcal{N}(A)=\{v\in V:\mathcal{N}(v)\cap A eq\emptyset\}$. The number $d_{c}(G)=\max\{\vert X\vert -\vert \mathcal{N}(X)\vert :X\subseteq V\}$ is called the critical difference of G, and A is critical if $\vert A\vert -\vert \mathcal{N}% (A)\vert =d_{c}(G)$ [C. Q. Zhang, SIAM J. Discrete Math., 3 (1990), pp. 431–438]. We define $\mathrm{\ker}(G)$ as the intersection of all critical sets. In this paper we prove that if $d_{c}(G)\geq1$, then $\mathrm{\ker}(G)\subseteq\mathrm{core}(G)$ and $\vert \mathrm{\ker}(G)\vert >d_{c}(G) \geq\alpha(G) -\mu(G)$.