Computing the hull number in toll convexity

Abstract Given a graph G, a set S ⊆ V ( G ) is Δ-convex if there is no vertex u ∈ V ( G ) ∖ S forming a triangle with two vertices of S. The Δ-convex hull of S is the minimum Δ-convex set containing S. The Δ-hull number of a graph G is the cardinality of a minimum set such that its Δ-convex hull is V ( G ) . We show that the problem of deciding whether the Δ-hull number of a general graph is at most k is an NP -complete problem and present polynomial-time algorithms for computing the Δ-hull number of some graph classes including chordal graphs, dually chordal graphs, and cographs.