CHARACTERISTIC PROPERTIES AND RECOGNITION OF GRAPHS IN WHICH GEODESIC AND MONOPHONIC CONVEXITIES ARE EQUIVALENT
Francesco Mario Malvestuto, Mauro Mezzini, Marina Moscarini · Discrete Mathematics Algorithms and Applications · 2012
Let G be a connected graph. A subset X of V(G) is g-convex (m-convex) if it contains all vertices on shortest (induced) paths between vertices in X. We state characteristic properties of graphs in which every g-convex set is m-convex, based on which we show that such graphs can be recognized in polynomial time. Moreover, we state a new convexity-theoretic characterization of Ptolemaic graphs.