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 $a(G \setminus x) < a(G)$. Note that if $a(G \setminus x) < a(G)$, then $a(G \setminus x)=a(G)-1$. Therefore, if there were such an algorithm, we could simply run it and then recurse to compute $a(G)$ in polynomial time.