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 \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)\}\).