k-independência em prismas complementares é NP-completo

• Otávio S. Mortosa UFG
• Márcia R. Cappelle UFG
• Erika Coelho UFG

DOI: https://doi.org/10.5753/etc.2022.223266

Resumo

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}^+$.

Palavras-chave: conjunto k-independente, prisma complementar, complexidade

Referências

Chellali, M., Favaron, O., Hansberg, A., and Volkmann, L. (2012). k-domination and k-independence in graphs: A survey. Graphs Combin., 28(1):1–55.

Duarte, M. A., Penso, L., Rautenbach, D., and dos Santos Souza, U. (2017). Complexity properties of complementary prisms. J. Comb. Optim, 33(2):365–372.

Fink, J. F. and Jacobson, M. S. (1985). On n-domination, n-dependence and forbidden subgraphs. In Graph theory with applications to algorithms and computer science, pages 301–311.

Jacobson, M. S. and Peters, K. (1989). Complexity questions for n-domination and related parameters. Congr. Numer., 68:7–22.

Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of computer computations, pages 85–103. Springer.

Mao, Y., Cheng, E., Wang, Z., and Guo, Z. (2018). The k-independence number of graph products. The Art of Discrete and Appl. Math., 1(1):P1–01.

Mortosa, O. S. and Cappelle, M. R. (2021). k-independence on complementary prism graphs. Matemática Contemporânea, 48:211–220.