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


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