Local Steiner convexity

Let GG be a connected graph and let SS be a set of vertices in GG. The Steiner distance d(S)d(S) of SS is the minimum size of a subtree of GG containing SS. Such a subtree of size d(S)d(S) is a Steiner tree for SS. The set SS is gg-convex if it contains the set of all vertices that lie on some shortest uu–vv path in GG for every pair uu and vv of vertices in SS. The set SS is kk-Steiner convex, denoted by gkgk-convex, if for every kk-element subset RR of SS, every vertex that belongs to some Steiner tree for RR is also in SS. Thus, SS is g2g2-convex if and only if it is gg-convex. In this paper, we distinguish three local convexity notions for g3g3-convexity and we characterize the graphs for which two of these conditions hold. For the third condition we determine some necessary conditions and some sufficient conditions for the graph class satisfying this condition.