Given a connected oriented graph D, we say that a subset S of V(D) is convex in D if, for every pair of vertices x, y in S, the vertex set of every x-y geodesic (x-y shortest dipath) and y-x geodesic in D is contained in S. The convexity number con (D) of a nontrivial connected oriented graph D is the maximum cardinality of a proper convex set of D. Let S_{C}(K_{n})={con(D)|D is an orientation of K_{n}} and S_{SC}(K_{n})={con(D)|D is a strong orientation of K_{n}}. We show that S_{C}(K_{3})={1,2} and S_{C}(K_{n})={1,3,4,...,n-1} if n >= 4. We also have that S_{SC}(K_{3})={1} and S_{SC}(K_{n})={1,3,4,...,n-2} if n >= 4 . We also show that every triple n, m, k of integers with n >= 5, 3 <= k <= n-2, and n+1 <= m <= n(n-1)/2, there exists a strong connected oriented graph D of order n with |E(D)|=m and con (D)=k.

Convexity in graphs has been widely discussed in graph theory and G. Chartrand et al. introduced the convexity number of oriented graphs in 2002. In this thesis, we follow the notions addressed by them and develop an extension in some related topics of convexity in directed graphs. Let D be a connected oriented graph. A set S subseteq V(D) is convex in D if, for every pair of vertices x, yin S, the vertex set of every x-y geodesic (x-y shortest directed path) and y-x geodesic in D is contained in S. The convexity number con(D) of a nontrivial oriented graph D is the maximum cardinality of a proper convex set of D. We show that for every possible triple n, m, k of integers except for k=4, there exists a strongly connected digraph D of order n, size m, and con(D)=k. Let G be a graph. We define the convexity spectrum S_{C}(G)={con(D): D is an orientation of G} and the strong convexity spectrum S_{SC}(G)={con(D): D is a strongly connected orientation of G}. Then S_{SC}(G) ⊆ S_{C}(G). We show that for any n ¡Ú 4, 1 ≤ a ≤ n-2 and a n ¡Ú 2, there exists a 2-connected graph G with n vertices such that S_C(G)=S_{SC}(G)={a,n-1}, and there is no connected graph G of order n ≥ 3 with S_{SC}(G)={n-1}. We also characterizes the convexity spectrum and the strong convexity spectrum of complete graphs, complete bipartite graphs, and wheel graphs. Those convexity spectra are of different kinds. Let the difference of convexity spectra D_{CS}(G)=S_{C}(G)- S_{SC}(G) and the difference number of convexity spectra dcs(G) be the cardinality of D_{CS}(G) for a graph G. We show that 0 ≤ dcs(G) ≤ ⌊|V(G)|/2⌋, dcs(K_{r,s})=⌊(r+s)/2⌋-2 for 4 ≤ r ≤ s, and dcs(W_{1,n-1})= 0 for n ≥ 5. The convexity spectrum ratio of a sequence of simple graphs G_n of order n is r_C(G_n)= liminflimits_{n to infty} frac{|S_{C}(G_n)|}{n-1}. We show that for every even integer t, there exists a sequence of graphs G_n such that r_C(G_n)=1/t and a formula for r_C(G) in subdivisions of G.

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&#8727; 3 . We show a relation between the geodetic convexity and the P&#8727; 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&#8727; 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&#8727; 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&#8727; 3 . We show a relation between the geodetic convexity and the P&#8727; 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&#8727; 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&#8727; 3 in graphs with few P4âs.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / In this work, we study some parameters of monophonic convexity in some classes of graphs and we present our results about this subject. We prove that decide if the $m$-interval number is at most 2 and decide if the $m$-percolation time is at most 1 are NP-complete problems even on bipartite graphs. We also prove that the $m$-convexity number is as hard to approximate as the maximum clique problem, which is, $O(n^{1-varepsilon})$-unapproachable in polynomial-time, unless P=NP, for each $varepsilon>0$. Finally, we obtain polynomial time algorithms to compute the $m$-convexity number on hereditary graph classes such that the computation of the clique number is polynomial-time solvable (e.g. perfect graphs and planar graphs). / Neste trabalho, estudamos alguns parÃmetros para a convexidade monofÃnica em algumas classes de grafos e apresentamos nossos resultados acerca do assunto. Provamos que decidir se o nÃmero de $m$-intervalo à no mÃximo 2 e decidir se o tempo de $m$-percolaÃÃo à no mÃximo 1 sÃo problemas NP-completos mesmo em grafos bipartidos. TambÃm provamos que o nÃmero de $m$-convexidade à tÃo difÃcil de aproximar quanto o problema da Clique MÃxima, que Ã, $O(n^{1-varepsilon})$-inaproximÃvel em tempo polinomial, a menos que P=NP, para cada $varepsilon>0$. Finalmente, apresentamos um algoritmo de tempo polinomial para determinar o nÃmero de $m$-convexidade em classes hereditÃrias de grafos onde a computaÃÃo do tamanho da clique mÃxima à em tempo polinomial (como grafos perfeitos e grafos planares).