Conjuntos k-independentes em alguns produtos de grafos
Guardado en:
| Autor principal: | |
|---|---|
| Fecha de Publicación: | 2022 |
| Formato: | Master thesis |
| Lenguaje: | por |
| Fuente: | Repositório Institucional da UFG |
| Download full: | http://repositorio.bc.ufg.br/tede/handle/tede/12059 |
Sumario: | 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. |
Ejemplares similares: Conjuntos k-independentes em alguns produtos de grafos
- Sobre grafos com r tamanhos diferentes de conjuntos independentes maximais e algumas extensões
- Interface para monitoramento elétrico com Mult-K 05 no contexto de Smart Campus
- Sistema de localização de facilidades: uma abordagem para mensuração de pontos de demanda e localização de facilidades
- Avaliação do potencial citotóxico, do perfil de morte celular in vitro e da atividade antitumoral in vivo induzidos pela resina floral e látex dos frutos de Clusia sp.
- Elementos extra-musicais na obra de K-ximbinho : questões sobre iconografia musical em suas capas de disco entre 1950 e 1960
- Análise comparativa de métodos de clusterização em dados geoespaciais