A note on \(\alpha\)-redundant vertices in graphs (Q5929313)

A vertex \(v\) of a graph \(G\) is called \(\alpha\)-redundant if \(\alpha (G-v)=\alpha (G)\) where \(\alpha (G)\) is the independence (stability) number of \(G\). The authors present sufficient conditions for the \(\alpha\)-redundancy. This leads to a polynomial-time algorithm which for any input graph outputs either its independence number or a forbidden configuration. Several previous results are improved (see e.g. \textit{A. Brandstädt} and \textit{P. L. Hammer} [Discrete Appl. Math. 95, No. 1-3, 163-167 (1999; Zbl 1113.05308)] and \textit{R. Mosca} [Inf. Process. Lett. 61, No. 3, 137-144 (1997)]).