Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/53442
Title in Portuguese: Números de envoltória e geodético em classes de grafos orientados.
Title: Envelope and geodetic numbers in oriented graph classes.
Author: Arraes, Pedro Santos Mota e
Advisor(s): Araújo, Júlio César Silva
Keywords: Número de envoltória
Número geodético
Grafos orientados
Convexidade em grafos
Hull number
Geodetic number
Oriented graphs
Convexity in graphs
Issue Date: 20-Feb-2020
Citation: ARRAES, Pedro Santos Mota e. Números de envoltória e geodético em classes de grafos orientados. 2020. 61 f. Dissertação (Mestrado Acadêmico em Matemática) – Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2020.
Abstract in Portuguese: Dado um grafo orientado D = (V, A), uma (u, v)-geodésica ´e um (u, v)-caminho (caminho do vértice u até o v) de menor comprimento. Um subconjunto de vértices S ⊆ V (D) é dito convexo quando esse contém os vértices de todas as (u, v)-geodésicas e de todas as (v, u)-geodésicas, com u, v ∈ S. A envoltória de um conjunto S ⊆ V (D), denotada por [S], é o menor conjunto convexo contendo S; essa também pode ser definida como a interseção de todos os conjuntos convexos que contêm S. Quando [S] = V (D) dizemos que S é um conjunto de envoltória de D, e o número de envoltória de D é a cardinalidade de um conjunto de envoltória mínimo. Caso cada vértice de D pertença a alguma (u, v)-geodésica com u, v ∈ S, dizemos que S é um conjunto geodético de D. Similarmente, o número geodético de D é a cardinalidade de um conjunto geodético mínimo. Nesta dissertação, além de revisarmos a literatura associada, apresentamos algumas contribuições para esses parâmetros em algumas classes de grafos orientados. A primeira é um limitante superior apertado para torneios, o qual estenderemos para grafos split orientados. Em seguida mostramos que os problemas relacionados a esses parâmetros são NP-completos para grafos bipartidos orientados. No caso do número de envoltória, isso também vale para uma subclasse de bipartidos: os cubos parciais. Para o número geodético, o grafo orientado utilizado na redução não só é bipartido, como também é um grafo direcionado acíclico. Por fim, provamos que é possível obter esses dois parâmetros em tempo polinomial para cactos orientados, uma superclasse de árvores orientadas.
Abstract: Given an oriented graph D = (V, A), an (u, v)-geodesic is an (u, v)-path (path from the vertex u to v) of smallest size. A vertex subset S ⊆ V (D) is convex whenever it contains the vertices of every (u, v)-geodesic and every (v, u)-geodesic, with u, v ∈ S. The hull of a set S ⊆ V (D), denoted by [S], is the smallest convex set containing S; it can also be defined as the intersection of all convex sets containing S. When [S] = V (D), we say that S is a hull set of D, and the hull number of D is the cardinality of a minimum hull set of D. In case each vertex of D belongs to some (u, v)-geodesic with u, v ∈ S, we say that S is a geodetic set of D. Similarly, the geodetic number of D is the cardinality of a minimum geodetic set. In this dissertation, besides reviewing the associated literature, we present a few contributions for these parameters in some classes of oriented graphs. The first one is a tight upper bound for tournaments, which we later extend for oriented split graphs. We also show that the decision problems related to these parameters are NP -complete for oriented bipartite graphs. For the hull number case, this is also true even if restricted do oriented partial cubes, a subclass of oriented bipartite graphs. As for the geodetic number, the oriented graph used in our reduction is not only bipartite, but is also a DAG. At last, we prove that it is possible to obtain both of these parameters in polynomial time when restricted to oriented cacti, a superclass of oriented trees.
URI: http://www.repositorio.ufc.br/handle/riufc/53442
metadata.dc.type: Dissertação
Appears in Collections:DMAT - Dissertações defendidas na UFC

Files in This Item:
File Description SizeFormat 
2020_dis_psmarraes.pdfdissertaçao pedro arraes466,58 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.