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).
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). |
Handle: | http://hdl.handle.net/11590/135756 |
Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.