Extreme Geodesic Graphs
For two vertices $u$ and $v$ of a graph $G$,
the {\it closed interval} $I[u, v]$ consists of
$u$, $v$, and all vertices lying in some $u-v$ geodesic of $G$,
while for $S \sbe V(G)$, the set $I[S]$
is the union of all sets $I[u, v]$ for
$u, v \in S$. A set $S$ of vertices of $G$ for which $I[S]=V(G)$ is a
geodetic set for $G$,
and the minimum cardinality of a geodetic set is the geodetic number
$g(G)$.
A vertex $v$ in $G$ is an extreme vertex if the subgraph induced by
its neighborhood is complete.
The number of extreme vertices in $G$ is
its extreme order $ex(G)$.
A graph $G$ is an extreme geodesic graph if $g(G) = ex(G)$,
that is, if every vertex lies on a $u-v$ geodesic for some
pair $u, v$ of extreme vertices.
It is shown that every pair $a, b$ of integers with $0 \leq a \leq b$
is realizable as the extreme order and geodetic number, respectively, of
some graph.
For positive integers $r, d,$ and $k \geq 2$,
it is shown that there exists
an extreme geodesic graph $G$ of radius $r$, diameter $d$, and
geodetic 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
connected extreme geodesic graph $G$ of order $n$, diameter $d$, and
geodetic number $k$. We show
that every graph of order $n$ with geodetic number $n-1$ is an extreme
geodesic graph.
On the other hand, for every pair $k, n$ of integers with $2 \leq k \leq
n-2$,
there exists a connected graph of order $n$ with geodetic number $k$
that is not an extreme geodesic graph.