DIMACS TR: 99-63
On the Number of Vertices Belonging to all Maximum Stable Sets of a Graph
Authors: E. Boros, M.C. Golumbic and V.E. Levit
ABSTRACT
Let us denote by $\alpha (G)$ the size of a maximum stable set,
and by $\mu(G)$ the size of a maximum matching of a graph $G$, and let $\xi
(G)$ be the number of vertices which belong to all maximum stable sets. We
shall show that $\xi (G)\geq 1+\alpha (G)-\mu (G)$ holds for any connected
graph, whenever $\alpha(G)>\mu(G)$.
This inequality improves on related results by Hammer, Hansen and Simeone
(1982) and by Levit and Mandrescu (1998). We also prove that on the one
hand, $\xi (G)>0$ can be recognized in polynomial time whenever $\mu
(G)<\left| V\left( G\right)\right|/3$, and on the other hand that
determining whether $\xi (G)>k$ is, in general, NP-complete for any fixed
$k\geq 0$.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-63.ps.gz
DIMACS Home Page