Conjuntos k-independentes em alguns produtos de grafos
Saved in:
| Main Author: | |
|---|---|
| Publication Date: | 2022 |
| Format: | Master thesis |
| Language: | por |
| Source: | Repositório Institucional da UFG |
| Download full: | http://repositorio.bc.ufg.br/tede/handle/tede/12059 |
Summary: | 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. |