On Closed and Upper Closed Geodetic Numbers of Graphs

Abstract

Let $G$ be a connected graph. For $S\subseteq V(G)$, the geodetic closure $I_G[S]$ of $S$ is the set of all vertices on geodesics (shortest paths) between two vertices of $S$. We select vertices of $G$ sequentially as follows: Select a vertex $v_1$ and let $S_1=\{v_1\}$. Select a vertex $v_2\ne v_1$ and let $S_2=\{v_1,v_2\}$. Then successively select vertex $v_i\notin I_G[S_{i-1}]$ and let $S_i=\{v_1,v_2,\dots ,v_i\}$. We define the closed geodetic number (resp. upper closed geodetic number) of $G$, denoted $cgn(G)$ (resp. $ucgn(G)$), to be the smallest (resp. largest) $k$ whose selection of $v_1,v_2,\dots ,v_k$ in the given manner yields $I_G[S_k]=V(G)$. In this paper, we show that for every pair $a,b$ of positive integers with $2\le a\le b$, there always exists a connected graph $G$ such that $cgn(G)=a$ and $ucgn(G)=b$, and if $a<b$, the minimum order of such graph $G$ is $b$. We characterize those connected graphs $G$ with the property: If $cgn(G)<k<ucgn(G)=6$, then there is a selection of vertices $v_1,v_2,\dots ,v_k$ as in the above manner such that $I_G[S_k]=V(G)$. We also determine the closed and upper closed geodetic numbers of some special graphs and the joins of connected graphs.