Please use this identifier to cite or link to this item: http://repositorio.ufc.br/handle/riufc/13355
Type: Dissertação
Title: Convexidades de caminhos e convexidades geométricas
Title in English: Convexities convexities of paths and geometric
Authors: Araújo, Rafael Teixeira de
Advisor: Sampaio, Rudini Menezes
Keywords: Teoria dos grafos;Grafos bipartidos
Issue Date: 2014
Citation: ARAÚJO, R. T. Convexidades de caminhos e convexidades geométricas. 2014. 51 f. Dissertação (Mestrado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2014.
Abstract: 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.
URI: http://www.repositorio.ufc.br/handle/riufc/13355
Appears in Collections:DCOMP - Dissertações defendidas na UFC

Files in This Item:
File Description SizeFormat 
2014_dis_rtaraujo.pdf973,82 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.