Local Steiner convexity

Let G be a connected graph and let S be a set of vertices in G. The Steiner distance d(S) of S is the minimum size of a subtree of G Containing S. Such a subtree of size d(S) is a Steiner tree for S. The set S is g-convex if it contains the set of all vertices that lie on some shortest u-v path in G for every pair u and v of vertices in S. The set S is k-Steiner convex, denoted by g(k)-convex, if for every k-element subset R of S, every vertex that belongs to some Steiner tree for R is also in S. Thus, S is g(2)-convex if and only if it is g-convex. In this paper, We distinguish three local convexity notions for g(1)-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. (C) 2008 Elsevier Ltd. All rights reserved.