Let V be a finite set and 𝓜 a collection of subsets of V. Then 𝓜 is an alignment of V if and only if 𝓜 is closed under taking intersections and contains both V and the empty set. If 𝓜 is an alignment of V, then the elements of 𝓜 are called convex sets and the pair (V,𝓜 ) is called an alignment or a convexity. If S ⊆ V, then the convex hull of S is the smallest convex set that contains S. Suppose X ∈ ℳ. Then x ∈ X is an extreme point for X if X∖{x} ∈ ℳ. 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)∖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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1638,
author = {Jose C\'aceres and Ortrud R. Oellermann and M. L. Puertas},
title = {Minimal trees and monophonic convexity},
journal = {Discussiones Mathematicae Graph Theory},
volume = {32},
year = {2012},
pages = {685-704},
zbl = {1293.05314},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1638}
}
Jose Cáceres; Ortrud R. Oellermann; M. L. Puertas. Minimal trees and monophonic convexity. Discussiones Mathematicae Graph Theory, Tome 32 (2012) pp. 685-704. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1638/
[000] [1] M. Atici, Computational complexity of geodetic set, Int. J. Comput. Math. 79 (2002) 587-591, doi: 10.1080/00207160210954. | Zbl 0999.05027
[001] [2] H.-J. Bandelt and H.M. Mulder, Distance-hereditary graphs, J. Combin. Theory (B) 41 (1986) 182-208, doi: 10.1016/0095-8956(86)90043-2. | Zbl 0605.05024
[002] [3] J.M. Bilbao and P.H. Edelman, The Shapley value on convex geometries, Discrete Appl. Math 103 (2000) 33-40, doi: 10.1016/S0166-218X(99)00218-8. | Zbl 0955.91002
[003] [4] A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A survey (SIAM Monogr. Discrete Math. Appl., Philidelphia, 1999).
[004] [5] J. Cáceres and O.R. Oellermann, On 3-Steiner simplicial orderings, Discrete Math. 309 (2009) 5825-5833, doi: 10.1016/j.disc.2008.05.047. | Zbl 1221.05042
[005] [6] J. Cáceres, O.R. Oellermann and M.L. Puertas, m₃³-convex geometries are A-free, arXiv.org 1107.1048, (2011) 1-15.
[006] [7] M. Changat and J. Mathew, Induced path transit function, monotone and Peano axioms, Discrete Math. 286 (2004) 185-194, doi: 10.1016/j.disc.2004.02.017. | Zbl 1056.05044
[007] [8] M. Changat, J. Mathew and H.M. Mulder, The induced path function, monotonicity and betweenness, Discrete Appl. Math. 158 (2010) 426-433, doi: 10.1016/j.dam.2009.10.004. | Zbl 1225.05146
[008] [9] G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs: Fifth Edition (Chapman and Hall, New York, 1996). | Zbl 0890.05001
[009] [10] F.F. Dragan, F. Nicolai and A. Brandstädt, Convexity and HHD-free graphs, SIAM J. Discrete Math. 12 (1999) 119-135, doi: 10.1137/S0895480195321718. | Zbl 0916.05060
[010] [11] M. Farber and R.E. Jamison, Convexity in graphs and hypergraphs, SIAM J. Alg. Discrete Meth. 7 (1986) 433-444, doi: 10.1137/0607049. | Zbl 0591.05056
[011] [12] E. Howorka, A characterization of distance hereditary graphs, Quart. J. Math. Oxford 28 (1977) 417-420, doi: 10.1093/qmath/28.4.417. | Zbl 0376.05040
[012] [13] B. Jamison and S. Olariu, On the semi-perfect elimination, Adv. in Appl. Math. 9 (1988) 364-376, doi: 10.1016/0196-8858(88)90019-X. | Zbl 0684.05020
[013] [14] E. Kubicka, G. Kubicki and O.R. Oellermann, Steiner intervals in graphs, Discrete Math. 81 (1998) 181-190, doi: 10.1016/S0166-218X(97)00084-X. | Zbl 0898.05044
[014] [15] M. Nielsen and O.R. Oellermann, Steiner trees and convex geometries, SIAM J. Discrete Math. 23 (2009) 680-693, doi: 10.1137/070691383. | Zbl 1191.05037
[015] [16] O.R. Oellermann, Convexity notions in graphs (2006) 1-4. http://www-ma2.upc.edu/seara/wmcgt06/.
[016] [17] O.R. Oellermann and M.L. Puertas, Steiner intervals and Steiner geodetic numbers in distance hereditary graphs, Discrete Math. 307 (2007) 88-96, doi: 10.1016/j.disc.2006.04.037. | Zbl 1113.05030
[017] [18] M.J.L. Van de Vel, Theory of convex structures (North-Holland, Amsterdam, 1993).