This monograph is intended to present the current state of the art of the so-called theory of
geodesic convexity in finite, simple, connected graphs. It has been designed with the …

We prove that the combinatorial optimization problem of determining the hull number of a
partial cube is NP-complete. This makes partial cubes the minimal graph class for which NP …

Let G be a finite, simple, and undirected graph and let S be a set of vertices of G. If no vertex
of G that does not belong to S has two neighbors in S, then S is P_3-convex. The P_3 …

In this paper, we study the geodetic convexity of graphs, focusing on the problem of the
complexity of computing a minimum hull set of a graph in several graph classes. For any two …

Convex Partitions of Graphs induced by Paths of Order Three CC Centeno1† S. Dantas2‡
MC Dourado1§ D. Rautenbach3¶ J. Page 1 Discrete Mathematics and Theoretical …

Partially answering a question posed by Araujo, Morel, Sampaio, Soares, and Weber, we
show that computing the geodetic hull number of a given P 9-free graph is NP-hard …

In this paper, we prove several inapproximability results on the P 3-convexity and the
geodesic convexity in graphs. We prove that determining the P 3-hull number and the …

Given a graph G and a pair of vertices u, v the interval IG [u, v] is the set of all vertices that
are in some shortest path between u and v. Given a subset X of vertices of G, the interval IG …

Inspired by a result of Carathéodory [Über den Variabilitätsbereich der Fourierschen
Konstanten von positiven harmonischen Funktionen, Rend. Circ. Mat. Palermo 32 (1911) …

In the geodetic convexity, a set of vertices S of a graph G is convex if all vertices belonging to
any shortest path between two vertices of S lie in S. The convex hull H (S) of S is the …