Independence and Irredundance in $k$-Regular Graphs

Abstract

We show that for each fixed $k\ge 3$, the $INDEPENDENTSET$ problem is $NP$-complete for the class of $k$-regular graphs. Several other decision problems, including $IRREDUNDANTSET$, are also $NP$-complete for each class of $k$-regular graphs, for $k\ge 6$.