Steiner Sets in Graphs



For a connected graph $G$ of order $n \geq 3$ and a set $W \sbe V(G)$, a tree $T$ contained in $G$ is a Steiner tree with respect to $W$ if $T$ is a tree of minimum order with $W \sbe V(T)$. The set $S(W)$ consists of all vertices in $G$ that lie on some Steiner tree with respect to $W$. The set $W$ is a Steiner set for $G$ if $S(W) = V(G)$. The minimum cardinality among the Steiner sets of $G$ is the Steiner number $s(G)$. For an integer $p \geq 1$, a set $W$ of vertices in a graph $G$ is $p$-uniform if the distance between every two distinct vertices of $W$ is $p$. A Steiner set $W$ in a graph $G$ is essential if for every Steiner $W$-tree $T$ in $G$, there exists a vertex of $G$ that lies on $T$ but on no other Steiner $W$-tree distinct from $T$. It is shown that for integers $k, p \geq 2$, there exists a connected graph $G$ with Steiner number $k$ such that $G$ contains a minimum $p$-uniform and essential Steiner set. A minimal Steiner set $W$ contains no proper Steiner subset. The maximum cardinality of a minimal Steiner set is the upper Steiner number $s^+ (G)$. Every pair $a, b$ of integers with $2 \leq a \leq b$ is realizable as the Steiner number and upper Steiner number of some connected graph. Connected graphs of order $n$ with upper Steiner number $n$ or $n-1$ are characterized. A Steiner set $W$ in a graph $G$ is extendable if $W-\{x\}$ is a Steiner set for every $x \in V(G) - W$. A necessary and sufficient condition for a Steiner set to be extendable is established.