Let G be a connected graph. A subset X of V(G) is g-convex (mconvex) 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.
Malvestuto, F., Mezzini, M., Moscarini, M. (2012). Characteristic properties and recognition of graphs in which geodesic and monophonic convexities are equivalent. DISCRETE MATHEMATICS, ALGORITHMS AND APPLICATIONS, 4(4) [10.1142/S1793830912500632].
Characteristic properties and recognition of graphs in which geodesic and monophonic convexities are equivalent
MEZZINI, MAURO;
2012-01-01
Abstract
Let G be a connected graph. A subset X of V(G) is g-convex (mconvex) 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
