Name
Abstract | ||
|---|---|---|
A finite convexity space is a pair (V,C) consisting of a finite set V and a set C of subsets of V such that 0@?@?C, V@?C, and C is closed under intersection. A graph G with vertex set V and a set P of paths of G naturally define a convexity space (V,C(P)) where C(P) contains all subsets C of V such that whenever C contains the endvertices of some path P in P, then C contains all vertices of P. We prove that for a finite convexity space (V,C) and a graph G with vertex set V, there is a set P of paths of G with C=C(P) if and only if *every set S which is not convex with respect to C contains two distinct vertices whose convex hull with respect to C is not contained in S and *for every two elements x and z of V and every element y distinct from x and z of the convex hull of {x,z} with respect to C, the subgraph of G induced by the convex hull of {x,z} with respect to C contains a path between x and z with y as an internal vertex. Furthermore, we prove that the corresponding algorithmic problem can be solved efficiently. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.disc.2010.12.024 | Discrete Mathematics |
Keywords | Field | DocType |
monophonic convexity,triangle-path convexity,convexity space,all-path convexity,geodetic convexity,convex hull | Discrete mathematics,Graph,Combinatorics,Convexity,Algorithmics,Finite set,Vertex (geometry),Vertex (graph theory),Convex hull,Regular polygon,Mathematics | Journal |
Volume | Issue | ISSN |
311 | 8-9 | Discrete Mathematics |
Citations | PageRank | References |
4 | 0.45 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mitre Dourado | 1 | 90 | 18.43 |
| Dieter Rautenbach | 2 | 946 | 138.87 |
| Philipp Matthias Schäfer | 3 | 26 | 4.46 |