×

Steiner trees and convex geometries. (English) Zbl 1191.05037

Summary: Let \(V\) be a finite set and \(\mathcal{M}\) a collection of subsets of \(V\). Then \(\mathcal{M}\) is an alignment of \(V\) if and only if \(\mathcal{M}\) is closed under taking intersections and contains both \(V\) and the empty set. If \(\mathcal{M}\) is an alignment of \(V\), then the elements of \(\mathcal{M}\) are called convex sets and the pair \((V,\mathcal{M})\) is called an aligned space. If \(S\subseteq V\), then the convex hull of \(S\) is the smallest convex set that contains \(S\). Suppose \(X\in\mathcal{M}\). Then \(x\in X\) is an extreme point for \(X\) if \(X\setminus \{x\} \in \mathcal{M}\). The collection of all extreme points of \(X\) is denoted by \(ex(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\) be a connected graph. A set \(S\) of vertices is \(g\)-convex if for every pair \(u,v\) of vertices in \(S\), every vertex that belongs to some \(u-v\) geodesic (shortest path) is also in \(S\). A set \(S\) of vertices in \(G\) is \(k\)-Steiner-convex, denoted by \(g_k\)-convex, if, for every set \(T\) of \(k\) vertices of \(S\), every vertex that belongs to some Steiner tree for \(T\), i.e., a subtree of \(G\) of smallest size containing \(T\), is also in \(S\). Let \(R=\{k_1,k_2,\cdots ,k_t\}\) be a collection of positive integers such that \(2\leq k_1<k_2<\cdots<k_t\). We say a set \(S\) of vertices in a connected graph is \(g_R\)-convex if \(S\) is \(g_{k_i}\)-convex for \(1\leq i\leq t\). A set \(S\) of vertices of \(G\) is \(g^3\)-convex if, for every pair \(u,v\) of vertices of \(S\), distance at least 3 apart in \(G\), every vertex that belongs to some \(u-v\) geodesic in \(G\) is also in \(S\). A set of vertices that is both \(g^3\)-convex and \(g_3\)-convex is called a \(g^3_3\)-convex set. Structural characterizations are given of those classes of graphs for which (i) the \(g_3\)-convex sets; (ii) the \(g_R\)-convex sets for those sets \(R\) that have minimum element 2 or 3; and (iii) the \(g^3_3\)-convex sets form a convex geometry.

MSC:

05C12 Distance in graphs
05C75 Structural characterization of families of graphs
05C17 Perfect graphs
52A01 Axiomatic and generalized convexity
PDFBibTeX XMLCite
Full Text: DOI