# Minimal trees and monophonic convexity

Jose Cáceres; Ortrud R. Oellermann; M. L. Puertas

Discussiones Mathematicae Graph Theory (2012)

- Volume: 32, Issue: 4, page 685-704
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJose Cáceres, Ortrud R. Oellermann, and M. L. Puertas. "Minimal trees and monophonic convexity." Discussiones Mathematicae Graph Theory 32.4 (2012): 685-704. <http://eudml.org/doc/271032>.

@article{JoseCáceres2012,

abstract = {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.},

author = {Jose Cáceres, Ortrud R. Oellermann, M. L. Puertas},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {minimal trees; monophonic intervals of sets; k-monophonic convexity; convex geometries; -monophonic convexity},

language = {eng},

number = {4},

pages = {685-704},

title = {Minimal trees and monophonic convexity},

url = {http://eudml.org/doc/271032},

volume = {32},

year = {2012},

}

TY - JOUR

AU - Jose Cáceres

AU - Ortrud R. Oellermann

AU - M. L. Puertas

TI - Minimal trees and monophonic convexity

JO - Discussiones Mathematicae Graph Theory

PY - 2012

VL - 32

IS - 4

SP - 685

EP - 704

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

LA - eng

KW - minimal trees; monophonic intervals of sets; k-monophonic convexity; convex geometries; -monophonic convexity

UR - http://eudml.org/doc/271032

ER -

## References

top- [1] M. Atici, Computational complexity of geodetic set, Int. J. Comput. Math. 79 (2002) 587-591, doi: 10.1080/00207160210954. Zbl0999.05027
- [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. Zbl0605.05024
- [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. Zbl0955.91002
- [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. Zbl1221.05042
- [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. Zbl1056.05044
- [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. Zbl1225.05146
- [9] G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs: Fifth Edition (Chapman and Hall, New York, 1996). Zbl0890.05001
- [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. Zbl0916.05060
- [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. Zbl0591.05056
- [12] E. Howorka, A characterization of distance hereditary graphs, Quart. J. Math. Oxford 28 (1977) 417-420, doi: 10.1093/qmath/28.4.417. Zbl0376.05040
- [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. Zbl0684.05020
- [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. Zbl0898.05044
- [15] M. Nielsen and O.R. Oellermann, Steiner trees and convex geometries, SIAM J. Discrete Math. 23 (2009) 680-693, doi: 10.1137/070691383. Zbl1191.05037
- [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. Zbl1113.05030
- [18] M.J.L. Van de Vel, Theory of convex structures (North-Holland, Amsterdam, 1993).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.