Números de envoltória e geodético em classes de grafos orientados.

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.