Independence and Irredundance in \(k\)-Regular Graphs

We show that for each fixed \(k \geq 3\), the \({INDEPENDENT \; SET}\) problem is \(NP\)-complete for the class of \(k\)-regular graphs. Several other decision problems, including \({IRREDUNDANT \; SET}\), are also \(NP\)-complete for each class of \(k\)-regular graphs, for \(k \geq 6\).