The Steiner Distance Dimension of Graphs

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=\{w_1, w_2, \cdots, w_k\}$ of vertices in a connected graph $G$ and a vertex $v$ of $G$, the Steiner representation $s(v | W)$ of $v$ with respect to $W$ is the $(2^k-1)$-vector $$s(v | W) = \left(d_1(v), d_2(v), \cdots, d_k(v), d_{1,2}(v), d_{1,3}(v), \cdots, d_{1,2,\cdots, k}(v) \right)$$ where $d_{i_1,i_2, \cdots, i_j}(v)$ is the Steiner distance $d(\{v, w_{i_1}, w_{i_2}, \cdots, w_{i_j}\})$. 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 $\dim_S(G)$. In this paper, we study the Steiner dimension of graphs and determine the Steiner dimensions of several classes of graphs.