Dades bibliogràfiques
| Autor principal: |
Nascimento, Julliano Rosa |
| Data de publicació: |
2016 |
| Format: |
Master thesis
|
| Idioma: |
por |
| Font: |
Repositório Institucional da UFG |
| Download full: |
http://repositorio.bc.ufg.br/tede/handle/tede/6583
|
Sumari: |
In this work, we consider the parameter hull number in two graph convexities, the P3- convexity and the geodetic convexity. In the P3-convexity, we present results on the P3- hull number on the Cartesian product, strong product and lexicographic product of graphs. In special, regarding to the Cartesian product, we proved a complexity result, in which we show, given a graph G resulting of a Cartesian product of two graphs and a positive integer k, is NP-complete to decide whether the P3-hull number of G is less than or equal k. We also consider the P3-hull number on complementary prisms GG of connected graphs G and G, in which we show a tighter upper bound than that found in the literature. In the geodetic convexity, we show results of the hull number on complementary prisms GG when G is a tree, when G is a disconnected graph and when G is a cograph. Finally, we also show that in the geodetic convexity, the hull number on the complementary prism GG is unlimited on connected graphs G and G, unlike what happens in the P3-convexity |
