Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs

Let G   be a connected graph and S⊆V(G)S⊆V(G). Then the Steiner distance of S  , denoted by dG(S)dG(S), is the smallest number of edges in a connected subgraph of G containing S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval for a set S   of vertices in a graph, denoted by I(S)I(S) is the union of all vertices that belong to some Steiner tree for S  . If S={u,v}S={u,v}, then I(S)I(S) is the interval I[u,v]I[u,v] between uu and vv. A connected graph G   is 3-Steiner distance hereditary (3-SDH3-SDH) if, for every connected induced subgraph H of order at least 3 and every set S of three vertices of H  , dH(S)=dG(S)dH(S)=dG(S). The eccentricity of a vertex vv in a connected graph G   is defined as e(v)=max{d(v,x)|x∈V(G)}e(v)=max{d(v,x)|x∈V(G)}. A vertex vv in a graph G   is a contour vertex if for every vertex uu adjacent with vv, e(u)⩽e(v)e(u)⩽e(v). The closure of a set S   of vertices, denoted by I[S]I[S], is defined to be the union of intervals between pairs of vertices of S taken over all pairs of vertices in S. A set of vertices of a graph G is a geodetic set if its closure is the vertex set of G. The smallest cardinality of a geodetic set of G is called the geodetic number of G   and is denoted by g(G)g(G). A set S of vertices of a connected graph G is a Steiner geodetic set for G   if I(S)=V(G)I(S)=V(G). The smallest cardinality of a Steiner geodetic set of G is called the Steiner geodetic number of G   and is denoted by sg(G)sg(G). We show that the contour vertices of 3-SDH3-SDH and HHDHHD-free graphs are geodetic sets. For 3-SDH3-SDH graphs we also show that g(G)⩽sg(G)g(G)⩽sg(G). An efficient algorithm for finding Steiner intervals in 3-SDH3-SDH graphs is developed.