k-independence in complementary prisms is NP-complete

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

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

Abstract

A set $S \subseteq V(G)$ of a graph $G$ is $k$-independent if every vertex in $S$ has at most $k-1$ neighbors in $S$, where $k \in \mathbb{Z}^+$. The $k$-independence number is the cardinality of a maximum $k$-independent set of a graph $G$. We present bounds for $k$-independence on complementary prisms and we show that deciding whether a complementary prism graph has a $k$-independent set of cardinality at least $\ell$ is a $\NPci$ problem, where $\ell \in \mathbb{Z}^+$.

Keywords: k-independent set, complementary prism, complexity

References

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.