###
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.