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.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:7701 |
| Date | 14 February 2014 |
| Creators | Rafael Teixeira de AraÃjo |
| Contributors | Rudini Menezes Sampaio, Fabricio Siqueira Benevides, Mitre Costa Dourado, Leonardo Sampaio Rocha |
| Publisher | Universidade Federal do CearÃ, Programa de PÃs-GraduaÃÃo em CiÃncia da ComputaÃÃo, UFC, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0026 seconds