Two classes of graphs in which some problems related to convexity are efficiently solvable

Monophonic, geodesic and 2-geodesic convexities (m-convexity, g-convexity and 2g-convexity, for short) on graphs are based on the families of induced paths, shortest paths and shortest paths of length 2, respectively. We introduce a class of graphs, the class of cross-cyclicgraphs, in which every connected 2g-convex set is also g-convex and m-convex. We show that this class is properly contained in the class, say Γ, of graphs in which geodesic and monophonic convexities are equivalent and properly contains the class of distance-hereditary graphs. Moreover, we show that (1) an m-hull set (i.e., a subset of vertices, with minimum cardinality, whose m-convex hull equals the whole vertex set) and, hence, the m-hull number and the g-hull number of a graph in Γ can be computed in polynomial time and that (2) both the geodesic-convex hull and the monophonic-convex hull can be computed in linear time in a cross-cyclic graph without cycles of length 3 and, hence, in a bipartite distance-hereditary graph.