O número envoltório P3 e o número envoltório geodético em produtos de grafos

• Ano de defesa: 2016
• Autor(a) principal: Nascimento, Julliano Rosa
• Orientador(a): Coelho, Erika Morais Martins
• Banca de defesa: Coelho, Erika Morais Martins , Szwarcfiter, Jayme Luiz , Centeno, Carmen Cecilia, Dias, Elisângela Silva
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Goiás
• Programa de Pós-Graduação: Programa de Pós-graduação em Ciência da Computação (INF)
• Departamento: Instituto de Informática - INF (RG)
• País: Brasil
• Palavras-chave em Português: Convexidade P3; Convexidade geodética; Número envoltório; Produtos de grafos; Prismas complementares
• Palavras-chave em Inglês: P3-convexity; Geodetic convexity; Hull number; Graph products; Complementary prisms
• Área do conhecimento CNPq: CIENCIA DA COMPUTACAO::MATEMATICA DA COMPUTACAO
• Link de acesso: http://repositorio.bc.ufg.br/tede/handle/tede/6583

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