On the number of vertices belonging to all maximum stable sets of a graph

Let us denote by a(G) the size of a maximum stable set, and by mu(G) the size of a maximum matching of a graph G, and let zeta(G) be the number of vertices which belong to all maximum stable sets. We shall show that xi(G) greater than or equal to 1 + alpha(G) - mu(G) holds for any connected graph, whenever alpha(G) > mu(G). This inequality improves on related results by Hammer et al. (SIAM J. Algebraic Discrete Methods 3 (1982) 511) and by Levit and Mandrescu [(prE-print math. CO/9912047 (1999) 13pp.)]. We also prove that on one hand, xi(G) > 0 can be recognized in polynomial time whenever mu(G) < \V(G)\/3, and on the other hand determining whether xi(G) > k is, in general, NP-complete for any fixed k greater than or equal to 0. (C) 2002 Elsevier Science B.V. All rights reserved.