On perfect and unique maximum independent sets in graphs.

*(English)*Zbl 1080.05527Summary: 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\).

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.) |