Independence and irredundance in \(k\)-regular graphs (Q2713623)

A subset of the vertex set \(V(G)\) of a graph \(G\) is independent, if it consists of pairwise non-adjacent vertices. A subset \(S\) of \(V(G)\) is irredundant, if for each \(u\in S\) there exists a vertex adjacent to \(u\) and to no other vertex of \(S\). The decision problem INDEPENDENT SET is the problem for a given graph \(G\) and a given integer \(m\) to decide, whether \(G\) has an independent set with at least \(m\) vertices. Analogously the problem IRREDUNDANT SET is defined. It is proved that INDEPENDENT SET (or IRREDUNDANT SET) is NP-complete in the class of all \(k\)-regular graphs for \(k \geq 3\) (or \(k \geq 6\) respectively).