# zbMATH — the first resource for mathematics

On perfect and unique maximum independent sets in graphs. (English) Zbl 1080.05527
Summary: A perfect independent set $$I$$ of a graph $$G$$ is defined to be an independent set with the property that any vertex not in  $$I$$ has at least two neighbors in  $$I$$. For a nonnegative integer $$k$$, a subset $$I$$ of the vertex set $$V (G)$$ of a graph $$G$$ is said to be  $$k$$-independent, if  $$I$$ is independent and every independent subset $$I'$$ of  $$G$$ with $$| I'| \geq | I| - (k - 1)$$ is a subset of  $$I$$. A set  $$I$$ of vertices of  $$G$$ is a super $$k$$-independent set of  $$G$$ if  $$I$$ is  $$k$$-independent in the graph $$G [I, V (G) - I]$$, where $$G [I, V (G) - I]$$ is the bipartite graph obtained from $$G$$ by deleting all edges which are not incident with vertices of $$I$$. It is easy to see that a set $$I$$ is $$0$$-independent if and only if it is a maximum independent set and 1-independent if and only if it is a unique maximum independent set of  $$G$$.
In this paper we mainly investigate connections between perfect independent sets and $$k$$-independent as well as super $$k$$-independent sets for $$k = 0$$ and $$k = 1$$.

##### MSC:
 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: