k-independência em prismas complementares é NP-completo - Mortosa, Otávio S.; Cappelle, Márcia R.; Coelho, Erika (Anais do Encontro de Teoria da Computação (ETC), 2022)
Um conjunto $S \subseteq V(G)$ de um grafo $G$ é $k$-independente se cada um de seus vértices é adjacente a no máximo $k - 1$ vértices do conjunto $S$, onde $k \in \mathbb{Z}^+$. O número de $k$-independência é a cardinalidade de um maior conjunto $k$-independente em um grafo $G$. Apresentamos limites para a $k$-independência em prismas complementares e mostramos que decidir se um grafo prisma complementar tem um conjunto $k$-independente de ordem pelo menos $\ell$ é um problema $\NPc$, onde $\ell \in \mathbb{Z}^+$.