Geodetic Sets in Graphs
For two vertices $u$ and $v$ of a graph $G$, the closed interval
$I[u, v]$ consists
of $u$, $v$, and
all vertices lying in 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$. If $I[S] = V(G)$, then
$S$ is a geodetic set for $G$. The geodetic number $g(G)$ is the minimum
cardinality of a geodetic set. A set $S$ of vertices in a graph
$G$ is uniform if the distance between every two distinct
vertices of $S$ is the same fixed number. A geodetic set is essential if for
every two distinct vertices
$u, v \in S$, there exists a third vertex $w$ of $G$ that lies in
some $u-v$ geodesic but in no $x-y$ geodesic for
$x, y \in S$ and $\{x, y\} \neq \{u, v\}$. It is shown that
for every integer $k \geq 2$, there exists a connected graph
$G$ with $g(G) = k$
which contains a uniform, essential minimum geodetic set.
A minimal geodetic set $S$ has no proper subset which is
a geodetic set. The
maximum cardinality of a minimal geodetic set is the upper
geodetic number $g^+ (G)$. It is
shown that every two integers $a$ and $b$ with $2 \leq a \leq b$ are
realizable as the
geodetic and upper geodetic numbers, respectively, of some graph and when
$a < b$ the minimum order of such a graph is $b+2$.