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 | Size | Format | |
---|---|---|---|---|
2014_dis_rtaraujo.pdf | 973,82 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.