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

Abstract

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

How to cite

top

Jose 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. [1] M. Atici, Computational complexity of geodetic set, Int. J. Comput. Math. 79 (2002) 587-591, doi: 10.1080/00207160210954. Zbl0999.05027
  2. [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. [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. [4] A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A survey (SIAM Monogr. Discrete Math. Appl., Philidelphia, 1999). 
  5. [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. [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. [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. [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. [9] G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs: Fifth Edition (Chapman and Hall, New York, 1996). Zbl0890.05001
  10. [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. [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. [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. [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. [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. [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. [16] O.R. Oellermann, Convexity notions in graphs (2006) 1-4. http://www-ma2.upc.edu/seara/wmcgt06/. 
  17. [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. [18] M.J.L. Van de Vel, Theory of convex structures (North-Holland, Amsterdam, 1993). 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.