For every pair of vertices $u,v$ in an oriented graph, a $u$-$v$ $geodesic$ is a shortest directed path from $u$ to $v$. For an oriented graph $D$, let $I_{D}[u,v]$ denoted the set of all vertices lying on a $u$-$v$ geodesic or a $v$-$u$ geodesic. And for $Ssubseteq V(D)$, let $I_{D}[S]$ denoted the union of all $I_{D}[u,v]$ for all $u,vin S$. If $S$ is a $convex$ set then $I_{D}[S]=S$. Let $[S]_{D}$ denoted the smallest convex set containing $S$. The $geodetic$ $number$ $g(D)$ of an oriented graph $D$ is the minimum cardinality of a set $S$ with $I_{D}[S]=V(D)$. The $hull$ $number$ $h(D)$ of an oriented graph $D$ is the minimum cardinality of a set $S$ with $[S]_{D}=V(D)$. For a connected graph $G$, let $g^{-}(G)=$min${g(D)$:$D$ is an orientation of $G$ $}$ and $g^{+}(G)=$max${g(D)$:$D$ is an orientation of $G$ $}$. And let $h^{-}(G)=$min${h(D)$:$D$ is an orientation of $G$ $}$ and $h^{+}(G)=$max${h(D)$:$D$ is an orientation of $G$ $}$. We show that $h^{+}(G)>h^{-}(G)$ and $g^{+}(G)>g^{-}(G)$ for every connected graph $G$ with $|V(G)|geq 3$. Then we show that $h^{+}(G)=h^{-}(G)+1$ if and only if $G$ is isomorphic to $K_{3}$ or $K_{1,r}$ for $rgeq 2$ and prove that for every connected graph $G$, $h^{+}(G)geq 5$ if and only if $|V(G)|geq 5$ and $G cong C_{5}$. Let $Sh^{*}(G)={h(D)$:$D$ is a strongly connected orientation of $G$ $}$ and we have $Sh^{*}(K_{n})={2}$. Let a graph $C(n,t)$ with $V(C(n,t))={1,2,...,n,x,y}$ and $E(C(n,t))={i(i+1):i=1,2,...,n-1}cup {1n}cup {1x}cup {ty}$. We also have $h^{-} (C(n,t))<g^{-}(C(n,t))<h^{+}(C(n,t)) =g^{+}(C(n,t))$ if $n geq 5$, $t eq frac{n}{2}$ and $3leq tleq n-1$. The last result answers a problem of Farrugia in [7].

CoordenaÃÃo de AperfeiÃoamento de NÃvel Superior / Esta tese à centrada no estudo de propriedades estruturais de grafos cujas compressÃes permitem a concepÃÃo de algoritmos eficientes para resolver problemas de otimizaÃÃo. Estamos particularmente interessados em decomposiÃÃes, em jogos de perseguiÃÃo-evasÃo e em convexidade. O jogo de Processo foi definido como um modelo para a reconfiguraÃÃo de roteamento em redes WDM. Muitas vezes, jogos de perseguiÃÃo-evasÃo, em que uma equipe de agentes tem como objetivo limpar um grafo nÃo direcionado, estÃo intimamente relacionados com decomposiÃÃes em grafos. No caso de grafos direcionados, mostramos que o jogo de Processo à monotÃnico e definimos uma nova decomposiÃÃo em grafos equivalente a tal jogo. A partir de entÃo, investigamos outras decomposiÃÃes em grafos. Propomos um algoritmo FPT para calcular vÃrios parÃmetros de largura em grafos. Em particular, este à o primeiro algoritmo FPT para calcular a largura em Ãrvore especial e a largura em Ãrvore q-ramificada de um grafo. Em seguida, estudamos um outro jogo perseguiÃÃo-evasÃo que modela problemas de prÃ-obtenÃÃo. NÃs introduzimos uma versÃo mais realista do jogo de VigilÃncia a versÃo on-line. Estudamos a diferenÃa entre o jogo de VigilÃncia clÃssico e suas versÃes conectadas e on-line, fornecendo novos limites para essa diferenÃa. NÃs, entÃo, definimos um modelo geral para o estudo de jogos perseguiÃÃo-evasÃo, com base em tÃcnicas de programaÃÃo linear. Este mÃtodo permite-nos dar os primeiros resultados de aproximaÃÃo para alguns desses jogos. Finalmente, estudamos outro parÃmetro relacionado com a convexidade e a propagaÃÃo da infecÃÃo em redes, o âhull numberâ. NÃs fornecemos vÃrios resultados de complexidade computacional, dependendo das propriedades estruturais do grafo de entrada e usando decomposiÃÃes em grafos. Alguns destes resultados respondem problemas em aberto na literatura. / This thesis focuses on the study of structural properties of graphs whose understanding enables the design of efficient algorithms for solving optimization problems. We are particularly interested in methods of decomposition, pursuit-evasion games and the notion of convexity. The Process game has been defined as a model for the routing reconfiguration problem in WDM networks. Often, such games where a team of searchers have to clear an undirected graph are closely related to graph decompositions. In digraphs, we show that the Process game is monotone and we define a new equivalent digraph decomposition. Then, we further investigate graph decompositions. We propose a unified FPT-algorithm to compute several graph width parameters. This algorithm turns to be the first FPTalgorithm for the special and the q-branched tree-width of a graph. We then study another pursuit-evasion game which models prefetching problems. We introduce the more realistic online variant of the Surveillance game. We investigate the gap between the classical Surveillance Game and its connected and online versions by providing new bounds. We then define a general framework for studying pursuit-evasion games, based on linear programming techniques. This method allows us to give first approximation results for some of these games. Finally, we study another parameter related to graph convexity and to the spreading of infection in networks, namely the hull number. We provide several complexity results depending on the graph structures making use of graph decompositions. Some of these results answer open questions of the literature.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2018-10-30T11:09:54Z No. of bitstreams: 2 Dissertação - Braully Rocha da Silva - 2018.pdf: 1396149 bytes, checksum: 9a9145cb07e037a784d2d15d43cbd1ff (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-10-30T11:20:36Z (GMT) No. of bitstreams: 2 Dissertação - Braully Rocha da Silva - 2018.pdf: 1396149 bytes, checksum: 9a9145cb07e037a784d2d15d43cbd1ff (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-10-30T11:20:36Z (GMT). No. of bitstreams: 2 Dissertação - Braully Rocha da Silva - 2018.pdf: 1396149 bytes, checksum: 9a9145cb07e037a784d2d15d43cbd1ff (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-09-24 / Outro / In this work we present results and implementantions for hull and Carathéodory numbers in P3 convexity. We obtain results for graphs of diameter 2 having cut-vertex for both problems. Finally, entering more complex cases, we were able to determine a logarithmic limit, means of algorithm, for the hull number in case of graph diameter 2 and 2-connected. Exploring more restrictive cases, we determined a constant limit for some subclasses of graphs of diameter 2. We made also implementations and algorithms for these parameters. Implementations algorithms heuristic, parallel, and brute force. Finally, although not directly related, we developed an algorithm for Moore's graphs generation, which may be one of the ways to find Moore missinge graph, if it exists, a question that remains unknown for 55 years. And finally, we conclude with some conjectures interesting, for limits to the hull and Carathéodory numbers, in other classes of graphs, that were not explored in this work, but was identified by the implementations, and can be better explored in future works. / Nesta dissertação, tratamos de limites para o número envoltório e o número de Carathéodory na Convexidade P3. Aferimos resultados para grafos de diâmetro 2 com vértice de corte para ambos os problemas. Adentrando em casos mais complexos, conseguimos determinar um limite logarítmico, por meio de algoritmo pseudo-polimonial, para o número envoltório de grafos de diâmetro 2 biconexos. Explorando um pouco mais restritivamente, conseguimos determinar um limite constante para algumas subclasses de grafos de diâmetro 2, os grafos maximais sem triângulo. Não atendo somente aos resultados teóricos, realizamos também implementações e algoritmos para esses parâmetros. As implementações perfazem algoritmos heurísticos, paralelos e força bruta. Por fim, embora não diretamente relacionado, desenvolvemos uma algoritmo para geração de grafos de Moore, que pode ser um dos caminhos para encontrar o ultimo grafo de Moore, caso ele exista. Questão que remanesce desconhecido e procurada por 55 anos.

Cette thèse porte sur l’étude des propriétés structurelles de graphes dont la compréhension permet de concevoir des algorithmes efficaces pour résoudre des problèmes d’optimisation. Nous nous intéressons plus particulièrement aux méthodes de décomposition des graphes, aux jeux de poursuites et à la notion de convexité. Le jeu de Processus a été défini comme un modèle de la reconfiguration de routage. Souvent, ces jeux où une équipe de chercheurs doit effacer un graphe non orienté sont reliés aux décompositions de graphes. Dans les digraphes, nous montrons que le jeu de Processus est monotone et nous définissons une nouvelle décomposition de graphes que lui est équivalente. Ensuite, nous étudions d’autres décompositions de graphes. Nous proposons un algorithme FPT-unifiée pour calculer plusieurs paramètres de largeur de graphes. En particulier, ceci est le premier FPT-algorithme pour la largeur arborescente q-branché et spéciale d’un graphe. Nous étudions ensuite un autre jeu qui modélise les problèmes de pré-chargement. Nous introduisons la variante en ligne du jeu de surveillance. Nous étudions l’écart entre le jeu de surveillance classique et ses versions connecté et en ligne, en fournissant de nouvelles bornes. Nous définissons ensuite un cadre général pour l’étude des jeux poursuite-évasion. Cette méthode nous permet de donner les premiers résultats d’approximation pour certains de ces jeux. Finalement, nous étudions un autre paramètre lié à la convexité des graphes et à la propagation d’infection dans les réseaux, le nombre enveloppe. Nous fournissons plusieurs résultats de complexité en fonction des structures des graphes et en utilisant des décompositions de graphes. / This thesis focuses on the study of structural properties of graphs whose understanding enables the design of efficient algorithms for solving optimization problems. We are particularly interested in methods of decomposition, pursuit-evasion games and the notion of convexity. The Process game has been defined as a model for the routing reconfiguration problem in WDM networks. Often, such games where a team of searchers have to clear an undirected graph are closely related to graph decompositions. In digraphs, we show that the Process game is monotone and we define a new equivalent digraph decomposition. Then, we further investigate graph decompositions. We propose a unified FPT-algorithm to compute several graph width parameters. This algorithm turns to be the first FPT-algorithm for the special and the q-branched tree-width of a graph. We then study another pursuit-evasion game which models prefetching problems. We introduce the more realistic online variant of the Surveillance game. We investigate the gap between the classical Surveillance Game and its connected and online versions by providing new bounds. We then define a general framework for studying pursuit-evasion games, based on linear programming techniques. This method allows us to give first approximation results for some of these games. Finally, we study another parameter related to graph convexity and to the spreading of infection in networks, namely the hull number. We provide several complexity results depending on the graph structures making use of graph decompositions. Some of these results answer open questions of the literature.

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.

Submitted by JÚLIO HEBER SILVA (julioheber@yahoo.com.br) on 2016-12-09T16:43:52Z No. of bitstreams: 2 Dissertação - Julliano Rosa Nascimento - 2016.pdf: 1812313 bytes, checksum: 9bdaa6ddbbe1dd9ce1e9ccdea8016eaf (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Jaqueline Silva (jtas29@gmail.com) on 2016-12-13T19:11:50Z (GMT) No. of bitstreams: 2 Dissertação - Julliano Rosa Nascimento - 2016.pdf: 1812313 bytes, checksum: 9bdaa6ddbbe1dd9ce1e9ccdea8016eaf (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2016-12-13T19:11:50Z (GMT). No. of bitstreams: 2 Dissertação - Julliano Rosa Nascimento - 2016.pdf: 1812313 bytes, checksum: 9bdaa6ddbbe1dd9ce1e9ccdea8016eaf (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-11-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this work, we consider the parameter hull number in two graph convexities, the P3- convexity and the geodetic convexity. In the P3-convexity, we present results on the P3- hull number on the Cartesian product, strong product and lexicographic product of graphs. In special, regarding to the Cartesian product, we proved a complexity result, in which we show, given a graph G resulting of a Cartesian product of two graphs and a positive integer k, is NP-complete to decide whether the P3-hull number of G is less than or equal k. We also consider the P3-hull number on complementary prisms GG of connected graphs G and G, in which we show a tighter upper bound than that found in the literature. In the geodetic convexity, we show results of the hull number on complementary prisms GG when G is a tree, when G is a disconnected graph and when G is a cograph. Finally, we also show that in the geodetic convexity, the hull number on the complementary prism GG is unlimited on connected graphs G and G, unlike what happens in the P3-convexity / Nesta dissertação, consideramos o parâmetro número envoltório em duas convexidades em grafos, a convexidade P3 e a convexidade geodética. Na convexidade P3, obtivemos resultados do número envoltório P3 para o produto Cartesiano, produto forte e produto lexicográfico de grafos. Em especial, em relação ao produto Cartesiano, obtivemos um resultado de complexidade, no qual mostramos que, dado um grafo G, resultante de um produto Cartesiano de dois grafos e um inteiro positivo k, é NP-completo decidir se o número envoltório P3 de G é menor ou igual a k. Também consideramos o número envoltório P3 para prismas complementares GG de grafos G e G conexos, em que mostramos um limite superior um pouco mais justo do que o encontrado na literatura. Na convexidade geodética, mostramos resultados do número envoltório para prismas complementares GG quando G é uma árvore, quando G é um grafo desconexo e quando G é um cografo. Por fim, também mostramos que na convexidade geodética o número envoltório do prisma complementar GG pode ser ilimitado para grafos G e G ambos conexos, diferentemente do que ocorre na convexidade P3.