On the Forcing Connected Geodetic Number and the Connected Geodetic Number of a Graph

Abstract

For two vertices \(u\) and \(v\) of a nontrivial connected graph \(G\), the set \(I[u,v]\) consists of all vertices lying on some \(u-v\) geodesic in \(G\), including \(u\) and \(v\). For \(S \subseteq V(G)\), the set \(Z[S]\) is the union of all sets \(I[u,v]\) for \(u,v \in S\). A set \(S \subseteq V(G)\) is a connected geodetic set of \(G\) if \(Z[S] = V(G)\) and the subgraph in \(G\) induced by \(S\) is connected. The minimum cardinality of a connected geodetic set of \(G\) is the connected geodetic number \(g_c(G)\) of \(G\) and a connected geodetic set of \(G\) whose cardinality equals \(g_c(G)\) is a minimum connected geodetic set of \(G\). A subset \(T\) of a minimum connected geodetic set \(S\) is a forcing subset for \(S\) if \(S\) is the unique minimum connected geodetic set of \(G\) containing \(T\). The forcing connected geodetic number \(f(S)\) of \(S\) is the minimum cardinality of a forcing subset of \(S\) and the forcing connected geodetic number \(f(G)\) of \(G\) is the minimum forcing connected geodetic number among all minimum connected geodetic sets of \(G\). Therefore, \(0 \leq f_c(G) \leq g_c(G)\). We determine all pairs \((a,b)\) of integers such that \(f_c(G) = a\) and \(gc(G) = b\) for some nontrivial connected graph \(G\). We also consider a problem of realizable triples of integers.