**
MATHEMATICA BOHEMICA, Vol. 129, No. 3, pp. 273-282 (2004)
**

#
On perfect and unique maximum independent

sets in graphs

##
Lutz Volkmann

* 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:**

[Previous Article] [Next Article] [Contents of this Number] [Journals Homepage]

*
© 2004–2010
FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition
*