2
$\begingroup$

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"?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • 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$ – Austin Buchanan Nov 2 '13 at 2:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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