Lutz Volkmann, Lehrstuhl II für Mathematik, RWTH Aachen, 52056 Aachen, Germany, e-mail: volkm@math2.rwth-aachen.de
Abstract: 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'|\ge|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$.
Keywords: independent sets, perfect independent sets, unique independent sets, strong unique independent sets, super unique independent sets
Classification (MSC2000): 05C70
Full text of the article: