Hull number: P5P5-free graphs and reduction rules

In this paper, we study the (geodesic) hull number of graphs. For any two vertices u,v∈Vu,v∈V of a connected undirected graph G=(V,E)G=(V,E), the closed interval I[u,v]I[u,v] of uu and vv is the set of vertices that belong to some shortest (u,v)(u,v)-path. For any S⊆VS⊆V, let I[S]=⋃u,v∈SI[u,v]I[S]=⋃u,v∈SI[u,v]. A subset S⊆VS⊆V is (geodesically) convex if I[S]=SI[S]=S. Given a subset S⊆VS⊆V, the convex hull Ih[S]Ih[S] of SS is the smallest convex set that contains SS. We say that SS is a hull set of GG if Ih[S]=VIh[S]=V. The size of a minimum hull set of GG is the hull number of GG, denoted by hn(G)hn(G).First, we show a polynomial-time algorithm to compute the hull number of any P5P5-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  GG, where the parameter can be the size of a vertex cover of GG 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.