Return to Revisions

It is unlikely that a nice characterization exists because the problem of computing the size of a maximum induced matching is a well-known NP-hard problem, even for bipartite graphs (as mentioned by Peter Heinig). Therefore, unless P=NP, there is no polynomial-time algorithm that can test if a given vertex $x$ satisfies $\alpha(G \setminus x) < \alpha(G)$. Note that if $\alpha(G \setminus x) < \alpha(G)$, then $\alpha(G \setminus x)=\alpha(G)-1$. Therefore, if there were such an algorithm, we could simply run it and then recurse to compute $\alpha(G)$ in polynomial time.