O número envoltório P3 e o número envoltório geodético em produtos de grafos
Uloženo v:
| Hlavní autor: | |
|---|---|
| Datum vydání: | 2016 |
| Médium: | Master thesis |
| Jazyk: | por |
| Zdroj: | Repositório Institucional da UFG |
| Download full: | http://repositorio.bc.ufg.br/tede/handle/tede/6583 |
Shrnutí: | 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 |
Podobné jednotky: O número envoltório P3 e o número envoltório geodético em produtos de grafos
- Algoritmos e limites para os números envoltório e de Carathéodory na convexidade P3
- Problema de particionamento em subgrafos complementares: complexidade e convexidade
- O número de Carathéodory na convexidade geodésica de grafos
- Sobre convexidade em prismas complementares
- Introdução à análise convexa: conjuntos e funções convexas
- Desigualdade de Díaz-Saá e aplicações