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.