On the Convexity of Paths of Length Two in Undirected Graphs

A subset S⊆V(G) of a graph G is p2 convex when v,w∈S and z∈V(G) imply z∈S, whenever v, z, w is a path of G. If S=V(G) then S is a p2 set of G. The size of the smallest p2 set of G is the p2 number of G, while the size of the largest proper p2 convex set is the p2 convexity number of G. On the other hand, for any given subset S of V(G), the smallest convex set Sh containing S is the p2 hull set of S. If Sh=V(G) then Sh is a p2 hull set of G. The size of the smallest p2 hull set is the p2 hull number of G. In this work, we prove the NP-hardness of the determination of p2 number and p2 convexity number of a graph, and describe polynomial time algorithms for trees, cographs and classes of grids.