On the computation of the hull number of a graph

Abstract

We prove that it is NP-hard to find the smallest cardinality set whose convex hull is the whole input graph. We also present polynomial-time algorithms for computing this number when the given is a unit interval graph, a cograph or a split graph.

Keywords

• computation
• number
• graph