Submitted by JÚLIO HEBER SILVA (julioheber@yahoo.com.br) on 2016-12-09T16:43:52Z
No. of bitstreams: 2
Dissertação - Julliano Rosa Nascimento - 2016.pdf: 1812313 bytes, checksum: 9bdaa6ddbbe1dd9ce1e9ccdea8016eaf (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Jaqueline Silva (jtas29@gmail.com) on 2016-12-13T19:11:50Z (GMT) No. of bitstreams: 2
Dissertação - Julliano Rosa Nascimento - 2016.pdf: 1812313 bytes, checksum: 9bdaa6ddbbe1dd9ce1e9ccdea8016eaf (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2016-12-13T19:11:50Z (GMT). No. of bitstreams: 2
Dissertação - Julliano Rosa Nascimento - 2016.pdf: 1812313 bytes, checksum: 9bdaa6ddbbe1dd9ce1e9ccdea8016eaf (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2016-11-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / 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 / Nesta dissertação, consideramos o parâmetro número envoltório em duas convexidades
em grafos, a convexidade P3 e a convexidade geodética. Na convexidade P3, obtivemos
resultados do número envoltório P3 para o produto Cartesiano, produto forte e produto
lexicográfico de grafos. Em especial, em relação ao produto Cartesiano, obtivemos um
resultado de complexidade, no qual mostramos que, dado um grafo G, resultante de um
produto Cartesiano de dois grafos e um inteiro positivo k, é NP-completo decidir se
o número envoltório P3 de G é menor ou igual a k. Também consideramos o número
envoltório P3 para prismas complementares GG de grafos G e G conexos, em que
mostramos um limite superior um pouco mais justo do que o encontrado na literatura.
Na convexidade geodética, mostramos resultados do número envoltório para prismas
complementares GG quando G é uma árvore, quando G é um grafo desconexo e quando
G é um cografo. Por fim, também mostramos que na convexidade geodética o número
envoltório do prisma complementar GG pode ser ilimitado para grafos G e G ambos
conexos, diferentemente do que ocorre na convexidade P3.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/6583 |
| Date | 30 November 2016 |
| Creators | Nascimento, Julliano Rosa |
| Contributors | Coelho, Erika Morais Martins, Szwarcfiter, Jayme Luiz, Coelho, Erika Morais Martins, Szwarcfiter, Jayme Luiz, Centeno, Carmen Cecilia, Dias, Elisângela Silva |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, -7712266734633644768, 1231144342511031835, 2075167498588264571 |
Page generated in 0.0029 seconds