Return to search

Convexities convexities of paths and geometric / Convexidades de caminhos e convexidades geomÃtricas

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.

Identiferoai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:7701
Date14 February 2014
CreatorsRafael Teixeira de AraÃjo
ContributorsRudini Menezes Sampaio, Fabricio Siqueira Benevides, Mitre Costa Dourado, Leonardo Sampaio Rocha
PublisherUniversidade Federal do CearÃ, Programa de PÃs-GraduaÃÃo em CiÃncia da ComputaÃÃo, UFC, BR
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Formatapplication/pdf
Sourcereponame:Biblioteca Digital de Teses e Dissertações da UFC, instname:Universidade Federal do Ceará, instacron:UFC
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0026 seconds