The Steiner Number of a Graph
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)$. Connected graphs of order $n$
with Steiner number $n$, $n-1$, or
2 are characterized.
It is shown that every pair $k, n$ of integers with $2 \leq k \leq n$
is realizable as the Steiner number and order of some connected graph.
For positive integers $r, d,$ and $k \geq 2$
with $r \leq d \leq 2r $, there exists a connected graph
of radius $r$, diameter $d$, and Steiner number $k$. Also, for integers $n,
d, $ and
$k$ with $2 \leq d < n$, $2 \leq k < n$, and $n -d - k +1 \geq 0$, there
exists a graph
$G$ of order $n$, diameter $d$, and Steiner number $k$.
For two vertices $u$ and $v$ of a connected graph $G$, the set $I(u, v)$
consists
of all vertices lying on some $u-v$ geodesic in $G$. For $U \sbe
V(G)$,
the set $I(U)$ is the union of all sets $I(u,v)$ for
$u, v \in U$. A set $U$ is a geodetic set if $I(U)=V(G)$. The cardinality
of a minimum geodetic set is the
geodetic number $g(G)$. It is shown that $g(G) \leq s(G)$ and that
for every pair $k, N$ of positive integers with
$k \geq 3$, there exists a connected graph $G$ with $g(G) = k$ such
that $s(G) - g(G) \geq N$.