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 ] = U u , v ∈ X J [ 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 c m ( G ) , is the cardinality of a maximum proper m-convex subset of V ( G ) . The smallest m-convex set containing X is denoted J h [ 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 J h [ 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 h m ( G ) , is the cardinality of a minimum m-hull set of G. In this work we study the complexity of computing the parameters c m ( G ) , m ( G ) and h m ( G ) .