A note on alpha-redundant vertices in graphs

A vertex v in a graph G is called alpha -redundant if alpha (G - v) = alpha (C), where alpha (G) stands for the stability number of G, i.e. the maximu m size of a subset of pairwise nonadjacent vertices. We describe sufficient conditions for a vertex to be alpha -redundant in terms of some P-4 extens ions. This leads to polynomial-time algorithms fur solving the stable set p roblem giving for an arbitrary input graph either the solution of the probl em or a forbidden configuration such as an induced P-5 or an induced banner in the input graph. The algorithms extend and improve a number of previous results on the problem. (C) 2001 Elsevier Science B.V. All rights reserved .