The Steiner distance dimension of graphs
Michael E. Raines, Ping Zhang · 1999
For a nonempty set S of vertices of a connected graph G, the Steiner distance d(S) of S is the minimum size among all connected subgraphs whose vertex set contains S. For an ordered set W = {Wl, W2,"', Wk} of vertices in a connected graph G and a vertex v of G, the Steiner representation s(vIW) of v with respect to W is the (2k- I)-vector where d i1,i2,...,ij(V) is the Steiner distance d({V,WipWi2,"',Wij}) ' The set W is a Steiner resolving set for G if, for every pair u, v of distinct vertices of G, U and v have distinct representations. A Steiner resolving set containing a minimum number of vertices is called a Steiner basis for G. The cardinality of a Steiner basis is the Steiner (distance) dimension dims (G). In this paper, we study the Steiner dimension of graphs and determine the Steiner dimensions of several classes of graphs. 1