Detalhes bibliográficos
| Ano de defesa: |
2014 |
| Autor(a) principal: |
Araújo, Rafael Teixeira de |
| Orientador(a): |
Sampaio, Rudini Menezes |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Não Informado pela instituição
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
http://www.repositorio.ufc.br/handle/riufc/13355
|
Resumo: |
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. |
