Well-covered graph

Well-covered graph --- хорошо покрытый граф.

Let [math]\displaystyle{ \beta }[/math], respectively [math]\displaystyle{ i }[/math], denote the maximum, respectively minimum, cardinality of a maximal independent set of [math]\displaystyle{ G }[/math]. A graph is mathcalled well-covered if for this graph [math]\displaystyle{ i = \beta and }[/math]\beta + \Delta = \lceil2\sqrt{n} - 1\rceil</math>. The problem of determining whether or not a graph is not well-covered is NP-complite.