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