Abstract   Let  G  be a finite, simple, and undirected graph and let  S  be a set of vertices of  G . If no vertex of  G  that does not belong to  S  has two neighbors in  S , then  S  is     P    3    -convex. The     P    3    -convex hull   H  (  S  )   of  S  is the smallest     P    3    -convex set containing  S . If   H  (  S  )  =  V  (  G  )   we say that  S  is a     P    3    -hull set of  G . The cardinality   h  (  G  )   of a minimum     P    3    -hull set in  G  is called the     P    3    -hull number of  G . In this paper w extend the result of Centeno et al. [Theoretical Computer Science 412 (2011), 3693–3700] showing that, given a graph G and an integer  k , deciding whether   h  (  G  )  ≤  k   remains NP-complete for the Cartesian product of graphs.
['Julliano R. Nascimento', 'Erika M. M. Coelho', 'Hebert Coelho', 'Jayme Luiz Szwarcfiter']
On the Complexity of the P3-Hull Number of the Cartesian Product of Graphs☆