ARAÚJO, Rafael Teixeira de. Convexidades de caminhos e convexidades geométricas. 2014. 52 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2014. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T16:01:23Z No. of bitstreams: 1 2014_dis_rtaraujo.pdf: 997190 bytes, checksum: 1adad553da251fa0f87bb80fbe452db4 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-21T16:02:42Z (GMT) No. of bitstreams: 1 2014_dis_rtaraujo.pdf: 997190 bytes, checksum: 1adad553da251fa0f87bb80fbe452db4 (MD5) / Made available in DSpace on 2016-07-21T16:02:42Z (GMT). No. of bitstreams: 1 2014_dis_rtaraujo.pdf: 997190 bytes, checksum: 1adad553da251fa0f87bb80fbe452db4 (MD5) Previous issue date: 2014 / In this dissertation we present complexity results related to the hull number and the convexity number for P3 convexity. We show that the hull number and the convexity number are NP-hard even for bipartite graphs. Inspired by our research in convexity based on paths, we introduce a new convexity, where we defined as convexity of induced paths of order three or P∗ 3 . We show a relation between the geodetic convexity and the P∗ 3 convexity when the graph is a join of a Km with a non-complete graph. We did research in geometric convexity and from that we characterized graph classes under some convexities such as the star florest in P3 convexity, chordal cographs in P∗ 3 convexity, and the florests in TP convexity. We also demonstrated convexities that are geometric only in specific graph classes such as cographs in P4+-free convexity, F free graphs in F-free convexity and others. Finally, we demonstrated some results of geodesic convexity and P∗ 3 in graphs with few P4’s. / Nessa dissertação apresentamos resultados de complexidade relativos ao número de hull e o número de convexidade na convexidade P3. Mostramos que o número de hull e o número de convexidade é NP-difícil mesmo em grafos bipartidos. Motivados por nossa pesquisa em convexidade baseada em caminhos introduzimos uma nova convexidade a qual definimos como convexidade dos caminhos induzidos de ordem três ou P∗ 3 . Mostramos uma relação da convexidade geodésica com a convexidade P∗ 3 no caso onde o grafo ´e uma jun¸c˜ao de um Km com um grafo n˜ao completo. Estudamos também convexidade geométrica e caracterizamos algumas classes de grafos em determinadas convexidade como as florestas de estrela na convexidade P3, cografos cordais na convexidade P∗ 3 , e as florestas na convexidade TP. Mostramos também convexidades que são geométricas somente em uma determinada classe de grafos como os cografos na convexidade P4+-free, os grafos livres de F na convexidade F-free entre outras. Por fim demonstramos alguns resultados de convexidade geodésica e P∗ 3 na em grafos com poucos P4’s.

FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico / In this dissertation we present complexity results related to the hull number and the convexity number for P3 convexity. We show that the hull number and the convexity number are NP-hard even for bipartite graphs. Inspired by our research in convexity based on paths, we introduce a new convexity, where we defined as convexity of induced paths of order three or P∗ 3 . We show a relation between the geodetic convexity and the P∗ 3 convexity when the graph is a join of a Km with a non-complete graph. We did research in geometric convexity and from that we characterized graph classes under some convexities such as the star florest in P3 convexity, chordal cographs in P∗ 3 convexity, and the florests in TP convexity. We also demonstrated convexities that are geometric only in specific graph classes such as cographs in P4+-free convexity, F free graphs in F-free convexity and others. Finally, we demonstrated some results of geodesic convexity and P∗ 3 in graphs with few P4âs. / In this dissertation we present complexity results related to the hull number and the convexity number for P3 convexity. We show that the hull number and the convexity number are NP-hard even for bipartite graphs. Inspired by our research in convexity based on paths, we introduce a new convexity, where we defined as convexity of induced paths of order three or P∗ 3 . We show a relation between the geodetic convexity and the P∗ 3 convexity when the graph is a join of a Km with a non-complete graph. We did research in geometric convexity and from that we characterized graph classes under some convexities such as the star florest in P3 convexity, chordal cographs in P∗ 3 convexity, and the florests in TP convexity. We also demonstrated convexities that are geometric only in specific graph classes such as cographs in P4+-free convexity, F free graphs in F-free convexity and others. Finally, we demonstrated some results of geodesic convexity and P∗ 3 in graphs with few P4âs.