Complexity results related to monophonic convexity

The study of monophonic convexity is based on the family of induced paths of a graph. The closure of a subset XX of vertices, in this case, contains every vertex vv such that vv belongs to some induced path linking two vertices of XX. Such a closure is called monophonic closure. Likewise, the convex hull of a subset is called monophonic convex hull  . In this work we deal with the computational complexity of determining important convexity parameters, considered in the context of monophonic convexity. Given a graph GG, we focus on three parameters: the size of a maximum proper convex subset of GG (m-convexity number  ); the size of a minimum subset whose closure is equal to V(G)V(G) (monophonic number  ); and the size of a minimum subset whose convex hull is equal to V(G)V(G) (m-hull number). We prove that the decision problems corresponding to the m-convexity and monophonic numbers are NP-complete, and we describe a polynomial time algorithm for computing the m-hull number of an arbitrary graph.