Extremal Problems in
Geodetic Graph Theory
For two vertices $u$ and $v$ of a graph $G$, the set $H(u, v)$ consists
of all vertices lying on some $u-v$ geodesic in $G$. For a
set $S$ of vertices of $G$, $H(S)$ is the union of all sets $H(u,v)$ for
$u, v \in S$. The geodetic number $g(G)$ is the minimum
cardinality among the subsets $S$ of $V(G)$ with $H(S)=V(G)$.
For integers $n$ and $m$ with
$n-1 \leq m \leq {n \choose 2}$, $\min (g; n, m)$ and $\max (g; n, m)$
represent the minimum and maximum geodetic numbers, respectively, among all
connected graphs of order $n$ and size $m$. It is shown that
$\min (g; n, m) =2$ unless $m = {n \choose 2}$. The number $\max(g; n, m)$
is investigated.