On the computation of the hull number of a graph

Let GG be a graph. If u,v∈V(G)u,v∈V(G), a u–vu–vshortest path   of GG is a path linking uu and vv with minimum number of edges. The closed interval   I[u,v]I[u,v] consists of all vertices lying in some u–vu–v shortest path of GG. For S⊆V(G)S⊆V(G), the set I[S]I[S] is the union of all sets I[u,v]I[u,v] for u,v∈Su,v∈S. We say that SS is a convex set   if I[S]=SI[S]=S. The convex hull   of SS, denoted Ih[S]Ih[S], is the smallest convex set containing SS. A set SS is a hull set   of GG if Ih[S]=V(G)Ih[S]=V(G). The cardinality of a minimum hull set of GG is the hull number   of GG, denoted by hn(G)hn(G). In this work we prove that deciding whether hn(G)≤khn(G)≤k is NP-complete.We also present polynomial-time algorithms for computing hn(G)hn(G) when GG is a unit interval graph, a cograph or a split graph.