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$.