O número envoltório P3 e o número envoltório geodético em produtos de grafos
Nenhuma Miniatura disponível
Data
2016-11-30
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
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
Descrição
Palavras-chave
Citação
NASCIMENTO, J. R. O número envoltório P3 e o número envoltório geodético em produtos de grafos. 2016. 87 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2016.