On the Geodetic Number of a Graph
For two vertices $u$ and $v$ of a graph $G$, the set $I(u, v)$ consists
of all vertices lying on some $u-v$ geodesic in $G$. If $S$ is a
set of vertices of $G$, then $I(S)$ is the union of all sets $I(u,v)$ for
$u, v \in S$. The geodetic number $g (G)$ is the minimum
cardinality among the subsets $S$ of $V(G)$ with $I(S)=V(G)$. It is shown
that
if $G$ is a graph of order $n$ and diameter $d$, then $g (G) \leq n-d+1$ and
this bound
is sharp. For positive integers $r, d,$ and $k \geq 2$
with $r \leq d \leq 2r $, there exists a connected graph
$G$ of radius $r$, diameter $d$, and $g (G) = 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 $g (G) = k$. It is shown, for every
nontrivial connected
graph $G$, that $g (G) \leq g (G \times K_2)$. A sufficient condition for
the
equality of $g (G)$ and $g (G \times K_2)$ is presented. A graph $F$ is a
minimum
geodetic subgraph if there exists a graph $G$ containing $F$ as induced
subgraph such that $V(F)$ is a minimum geodetic set for $G$. Minimum
geodetic subgraphs are characterized.