Artículo
Steiner distance and convexity in graphs
Autor/es | Cáceres González, José
Márquez Pérez, Alberto Puertas González, María Luz |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2008 |
Fecha de depósito | 2016-02-12 |
Publicado en |
|
Resumen | 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 ... 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. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Steiner distance.pdf | 396.7Kb | [PDF] | Ver/ | |