Cáceres, Jose; Oellermann, Ortrud R.; Puertas, M. L. Minimal trees and monophonic convexity. (English) Zbl 1293.05314 Discuss. Math., Graph Theory 32, No. 4, 685-704 (2012). Summary: Let \(V\) be a finite set and \(M\) a collection of subsets of \(V\). Then \(M\) is an alignment of \(V\) if and only if \(M\) is closed under taking intersections and contains both \(V\) and the empty set. If \(M\) is an alignment of \(V\), then the elements of \(M\) are called convex sets and the pair \((V,M)\) is called an alignment or a convexity. If \(S\subseteq V\), then the convex hull of \(S\) is the smallest convex set that contains \(S\). Suppose \(X\in M\). Then \(x\in X\) is an extreme point for \(X\) if \(X\setminus \{x\}\in M\). A convex geometry on a finite set is an aligned space with the additional property that every convex set is the convex hull of its extreme points. Let \(G = (V,E)\) be a connected graph and \(U\) a set of vertices of \(G\). A subgraph \(T\) of \(G\) containing \(U\) is a minimal \(U\)-tree if \(T\) is a tree and if every vertex of \(V(T)\setminus U\) is a cut-vertex of the subgraph induced by \(V(T)\). The monophonic interval of \(U\) is the collection of all vertices of \(G\) that belong to some minimal \(U\)-tree. Several graph convexities are defined using minimal \(U\)-trees and structural characterizations of graph classes for which the corresponding collection of convex sets is a convex geometry are characterized. Cited in 6 Documents MSC: 05C75 Structural characterization of families of graphs 05C12 Distance in graphs 05C17 Perfect graphs 05C05 Trees Keywords:minimal trees; monophonic intervals of sets; \(k\)-monophonic convexity; convex geometries PDFBibTeX XMLCite \textit{J. Cáceres} et al., Discuss. Math., Graph Theory 32, No. 4, 685--704 (2012; Zbl 1293.05314) Full Text: DOI