The Geodetic Number of an Oriented Graph
For two vertices $u$ and $v$ of an oriented graph $D$,
the set $I(u, v)$ consists
of all vertices lying on a $u-v$ geodesic or $v-u$ geodesic in $D$. If
$S$ is a
set of vertices of $D$, then $I(S)$ is the union of all sets $I(u,v)$ for
vertices
$u$ and $v$ in $S$. The geodetic number $g(D)$ is the minimum
cardinality among the subsets $S$ of $V(D)$ with $I(S)=V(D)$.
Several results concerning the geodetic numbers of
connected oriented graphs
are presented.
For a nontrivial connected graph $G$,
the lower orientable geodetic number
$g^-(G)$ of $G$ is the minimum geodetic number among the orientations of
$G$ and
the upper orientable geodetic number
$g^+(G)$ is the maximum such geodetic number.
It is shown that $g^- (G) \neq g^+(G)$ for every connected graph of order
at least 3.
The lower and upper orientable geodetic numbers of
several well known classes of graphs are determined. It is shown that for
every two
integers $n$ and $m$ with $1 \leq n-1 \leq m \leq {n \choose 2}$,
there exists a connected graph $G$ of order $n$ and size $m$ such that
$g^+(G) = n$.