The Forcing 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$. A set $S$ is a geodetic set if $I(S)=V(G)$. A minimum geodetic set is a geodetic set of minimum cardinality and this cardinality is the geodetic number $g(G)$. A subset $T$ of a minimum geodetic set $S$ is called a forcing subset for $S$ if $S$ is the unique minimum geodetic set containing $T$. The forcing geodetic number $f_{G}(S)$ of $S$ is the minimum cardinality among the forcing subsets of $S$, and the forcing geodetic number $f(G)$ of $G$ is the minimum forcing geodetic number among all minimum geodetic sets of $G$. The forcing geodetic numbers of several classes of graphs are determined. For every graph $G$, $f(G) \leq g(G)$. It is shown that for all integers $a, b$ with $0\leq a\leq b$, a connected graph $G$ such that $f(G)=a$ and $g(G)=b$ exists if and only if $(a,b)\notin\{(1,1),(2,2)\}$.