On perfect and unique maximum independent sets in graphs. (English) Zbl 1080.05527

Volkmann, Lutz

Math. Bohem. 129, No. 3, 273-282 (2004).

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

Keywords:

independent sets; perfect independent sets; unique independent sets; strong unique independent sets; super unique independent sets