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.