Geodesic
Minimal trees and monophonic convexity
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 685-704.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: minimal trees, monophonic intervals of sets, k-monophonic convexity, convex geometries 
@article{DMGT_2012_32_4_a6,
     author = {C\'aceres, Jose and Oellermann, Ortrud and Puertas, M.},
     title = {Minimal trees and monophonic convexity},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {685--704},
     publisher = {mathdoc},
     volume = {32},
     number = {4},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a6/}
}
TY  - JOUR
AU  - Cáceres, Jose
AU  - Oellermann, Ortrud
AU  - Puertas, M.
TI  - Minimal trees and monophonic convexity
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 685
EP  - 704
VL  - 32
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a6/
LA  - en
ID  - DMGT_2012_32_4_a6
ER  - 
%0 Journal Article
%A Cáceres, Jose
%A Oellermann, Ortrud
%A Puertas, M.
%T Minimal trees and monophonic convexity
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 685-704
%V 32
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a6/
%G en
%F DMGT_2012_32_4_a6
Cáceres, Jose; Oellermann, Ortrud; Puertas, M. Minimal trees and monophonic convexity. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 685-704. http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a6/

[1] M. Atici, Computational complexity of geodetic set, Int. J. Comput. Math. 79 (2002) 587-591, doi: 10.1080/00207160210954.

[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.

[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.

[4] A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A survey (SIAM Monogr. Discrete Math. Appl., Philidelphia, 1999).

[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.

[6] J. Cáceres, O.R. Oellermann and M.L. Puertas, m₃³-convex geometries are A-free, arXiv.org 1107.1048, (2011) 1-15.

[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.

[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.

[9] G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs: Fifth Edition (Chapman and Hall, New York, 1996).

[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.

[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.

[12] E. Howorka, A characterization of distance hereditary graphs, Quart. J. Math. Oxford 28 (1977) 417-420, doi: 10.1093/qmath/28.4.417.

[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.

[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.

[15] M. Nielsen and O.R. Oellermann, Steiner trees and convex geometries, SIAM J. Discrete Math. 23 (2009) 680-693, doi: 10.1137/070691383.

[16] O.R. Oellermann, Convexity notions in graphs (2006) 1-4. http://www-ma2.upc.edu/seara/wmcgt06/.

[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.

[18] M.J.L. Van de Vel, Theory of convex structures (North-Holland, Amsterdam, 1993).