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