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\le f_c(G)\le 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.