The Upper Forcing Geodetic Number of a Graph



For vertices $u$ and $v$ in a nontrivial connected graph $G$, the closed interval $I[u, v]$ consists of $u$, $v$, and all vertices lying in some $u-v$ geodesic of $G$. For $S \sbe V(G)$, the set $I[S]$ is the union of all sets $I[u, v]$ for $u, v \in S$. A set $S$ of vertices of a graph $G$ is a geodetic set in $G$ if $I[S]=V(G)$. The minimum cardinality of a geodetic set in $G$ is its geodetic number $g(G)$. A subset $T$ of a minimum geodetic set $S$ in a graph $G$ is a forcing subset for $S$ if $S$ is the unique minimum geodetic set containing $T$. The forcing geodetic number $f(S)$ of $S$ in $G$ is the minimum cardinality of a forcing subset for $S$, and the upper forcing geodetic number $f^+(G)$ of the graph $G$ is the maximum forcing geodetic number among all minimum geodetic sets of $G$. Thus $0 \leq f^+(G) \leq g(G)$ for every graph $G$. The upper forcing geodetic numbers of several classes of graphs are determined. It is shown that for every pair $a, b$ of integers with $0 \leq a \leq b$ and $b \geq 1$, there exists a connected graph $G$ with $f^+(G) = a$ and $g(G) = b$ if and only if $(a, b) \notin \{(1, 1), (2, 2)\}$.