Conjuntos k-independentes em alguns produtos de grafos

• Ano de defesa: 2022
• Autor(a) principal: Mortosa, Otávio Soares
• Orientador(a): Santana, Márcia Rodrigues Cappelle
• Banca de defesa: Nascimento, Julliano Rosa, Coelho, Erika Morais Martins, Bravo, Raquel de Souza Francisco, Santana, Márcia Rodrigues Cappelle
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Goiás
• Programa de Pós-Graduação: Programa de Pós-graduação em Ciência da Computação (INF)
• Departamento: Instituto de Informática - INF (RG)
• País: Brasil
• Palavras-chave em Português: Conjuntos k-independentes; K-independência; Produtos de grafos
• Palavras-chave em Inglês: K-independent sets; K-indepence; Graph products
• Área do conhecimento CNPq: CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::MATEMATICA DA COMPUTACAO
• Link de acesso: http://repositorio.bc.ufg.br/tede/handle/tede/12059

A subset S of vertices of a graph G is k-independent if every vertex in S has less than k neighbors in S, k being a positive integer. Given a graph G and integers k and ell, the “k-independent set” problem consists in deciding whether G has a k-independent set with cardinality at least ell. This problem is NP-complete. We present improvements for some lower and upper bounds of maximal k-independent sets on lexicographic, Cartesian products and and complementary prisms, in comparison with some results already present in the literature. Specifically, for the lexicographic product, we improve the upper bound for the maximum cardinality of 2-independent sets in general graphs. On the Cartesian product, we show better bounds for the maximum cardinality of k-independent sets on grids graphs. For the complementary prisms, we show extensions and generalizations for the maximum cardinality of k-independent sets in general graphs and closed formulas for some especific classes. Lastly, we prove that “k-independent set” remains NP-complete even when restricted to complementary prisms.