1 |
Convexities convexities of paths and geometric / Convexidades de caminhos e convexidades geomÃtricasRafael Teixeira de AraÃjo 14 February 2014 (has links)
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.
|
Page generated in 0.0594 seconds