Complexity results on \(k\)-independence in some graph products (Q6594024)

For a positive integer \(k\), a subset \(S\) of vertices of a graph \(G\) is \(k\)-independent if each vertex in \(S\) has at most \(k-1\) neighbors in \(S\). The maximum cardinality of a maximal \(k\)-independent set of a graph \(G\) is denoted by \(\alpha_k(G)\), called the \(k\)-independence number. For a given fixed integer \(k\ge 1\), the \(k\)-independent set decision problem is defined as follows.\N\N\(k\)-independent\N\NInstance: A graph \(G\) and a positive integer \(\ell\), where \(\Delta(G)\ge \ell\) and \(\ell\ge k\).\N\NQuestion: Does \(G\) have a \(k\)-independent set of size at least \(\ell\)?\N\NIn this paper, the \(k\)-independent sets in Cartesian products and complementary prism are considered and it is shown that the problem of determining \(k\)-independence remains NP-complete even for Cartesian products and complementary prisms. Moreover, some results on \(4\)-independence number are presented for grids.