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].
Titolo: | Characteristic properties and recognition of graphs in which geodesic and monophonic convexities are equivalent | |
Autori: | ||
Data di pubblicazione: | 2012 | |
Rivista: | ||
Citazione: | 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]. | |
Handle: | http://hdl.handle.net/11590/135756 | |
Appare nelle tipologie: | 1.1 Articolo in rivista |