On the hull number of some graph classes

Given a graph G=(V,E), the closed interval of a pair of vertices u,v∈V, denoted by I[u,v], is the set of vertices that belongs to some shortest (u,v)-path. For a given S⊆V, let I[S]=⋃u,v∈SI[u,v]. We say that S⊆V is a convex set if I[S]=S.The convex hull Ih[S] of a subset S⊆V is the smallest convex set that contains S. We say that S is a hull set if Ih[S]=V. The cardinality of a minimum hull set of G is the hull number of G, denoted by hn(G).We show that deciding if hn(G)⩽k is an NP-complete problem, even if G is bipartite. We also prove that hn(G) can be computed in polynomial time for cactus and P4-sparse graphs.