Algorithmic Aspects of Monophonic Convexity

Let G be a graph, and u,v∈V(G). The monophonic interval J[u,v] is the set of vertices of all induced paths linking u and v. If X⊆V(G), the monophonic closure J[X] of X is defined as J[X]=Uu,v∈XJ[u,v]. In addition, if X=J[X] then X is said to be monophonically convex or simply m-convex. The m-convexity number of G, denoted by cm(G), is the cardinality of a maximum proper m-convex subset of V(G). The smallest m-convex set containing X is denoted Jh[X] and called m-convex hull of X. A subset X⊆V(G) is called a monophonic set if J[X]=V(G), and an m-hull set if Jh[X]=V(G). The monophonic number of G, denoted by m(G), is the cardinality of a minimum monophonic set of G, and the m-hull number of G, denoted by hm(G), is the cardinality of a minimum m-hull set of G. In this work we study the complexity of computing the parameters cm(G), m(G) and hm(G).