Complexity of determining the maximum infection time in the geodetic convexity

In the geodetic convexity of a graph G, we define the interval of a set S⊆V(G) as the set formed by S and all vertices in all shortest paths with endpoints in S. We say S is convex if it is equal to its interval. The convex hull of S can be obtained by repeatedly applying the interval function until obtaining a convex set. Here we consider the problem of determining the maximum k such that there is a set of vertices S, whose convex hull is V (G), such that it is necessary at least k applications of the interval function to obtain V (G). We show that this problem is NP-complete for bipartite graphs and give a polynomial time algorithm for distance-hereditary graphs.