Repositorio de producción científica de la Universidad de Sevilla

Steiner distance and convexity in graphs

 

Advanced Search
 
Opened Access Steiner distance and convexity in graphs
Cites

Show item statistics
Icon
Export to
Author: Cáceres González, José
Márquez Pérez, Alberto
Puertas González, María Luz
Department: Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
Date: 2008
Published in: European Journal of Combinatorics, 29 (3), 726-736.
Document type: Article
Abstract: We use the Steiner distance to define a convexity in the vertex set of a graph, which has a nice behavior in the well-known class of HHD-free graphs. For this graph class, we prove that any Steiner tree of a vertex set is included into the geodesical convex hull of the set, which extends the well-known fact that the Euclidean convex hull contains at least one Steiner tree for any planar point set. We also characterize the graph class where Steiner convexity becomes a convex geometry, and provide a vertex set that allows us to rebuild any convex set, using convex hull operation, in any graph.
Size: 396.7Kb
Format: PDF

URI: http://hdl.handle.net/11441/34681

DOI: http://dx.doi.org/10.1016/j.ejc.2007.03.007

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)