Hull number: -free graphs and reduction rules

In this paper, we study the (geodesic) hull number of graphs. For any two vertices u , v ∈ V of a connected undirected graph G = ( V , E ) , the closed interval I [ u , v ] of u and v is the set of vertices that belong to some shortest ( u , v ) -path. For any S ⊆ V , let I [ S ] = ⋃ u , v ∈ S I [ u , v ] . A subset S ⊆ V is (geodesically) convex if I [ S ] = S . Given a subset S ⊆ V the convex hull I h [ S ] of S is the smallest convex set that contains S. We say that S is a hull set of G if I h [ S ] = V . The size of a minimum hull set of G is the hull number of G, denoted by h n ( G ) . we show a polynomial-time algorithm to compute the hull number of any P 5 -free triangle-free graph. Then, we present four reduction rules based on vertices with the same neighborhood. We use these reduction rules to propose a fixed parameter tractable algorithm to compute the hull number of any graph G, where the parameter can be the size of a vertex cover of G or, more generally, its neighborhood diversity, and we also use these reductions to characterize the hull number of the lexicographic product of any two graphs.