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 \neq 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, \ldots, 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, \ldots, 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 \leq a \leq 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, \ldots, 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.