On finite convexity spaces induced by sets of paths in graphs
| Autor: | Mitre Costa Dourado, Philipp Matthias Schäfer, Dieter Rautenbach |
|---|---|
| Rok vydání: | 2011 |
| Předmět: |
Convex hull
Vertex (graph theory) Discrete mathematics Geodetic convexity Regular polygon Convexity space Triangle-path convexity Graph Convexity Theoretical Computer Science Combinatorics Algorithmics Monophonic convexity All-path convexity Discrete Mathematics and Combinatorics Finite set Mathematics |
| Zdroj: | Discrete Mathematics. 311:616-619 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2010.12.024 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect