The Upper Forcing Geodetic Number of a Graph

Abstract

For vertices $u$ and $v$ in a nontrivial connected graph $G$, the closed interval $[u,v]$ consists of $u$, $v$, and all vertices lying in some $u-v$ geodesic of $G$. For $S\subseteq 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\le f^{+}(G)\le 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\le a\le b$ and $b\ge 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)\}$.