An independent set is a set of vertices in a graph, no two of which are adjacent.

A maximum independent set is a largest independent set for a given graph G.

Is there a standard term for the size of the largest independent set in a given graph?

If not, what short term can you suggest for this size? Maybe "independence number"?


1 Answer 1


Yes, it's called the independence number and it's usually denoted $\alpha(G)$.

  • 1
    $\begingroup$ This is probably the most common term. Another fairly common term is stability number, though this is used when referring to stable sets. $\endgroup$ Commented Nov 2, 2013 at 2:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.