On the geodetic number of a graph (Q2782725)

For two vertices \(u\) and \(v\) of a graph \(G\), let the set \(I(u,v)\) consist of all vertices lying on some \(u\)-\(v\) geodesic in \(G\). If \(S\) is a nonempty subset of vertices of \(G\), then \(I(S)=\bigcup_{u,v\in S}I(u,v)\). The geodetic number \(\text{gd}(G)\) of \(G\)is the minimum cardinality among the subsets \(S\) of \(V(G)\) with \(I(S)=V(G)\). In this paper it is shown that if \(G\) is a graph of order \(n\) and diameter \(d\) then \(\text{gd}(G)\leq n-d+1\) and this bound is sharp and for positive integers \(r\), \(d\), and \(k\geq 2\) with \(r\leq d\leq 2r\), there exists a connected graph \(G\) of radius \(r\), diameter \(d\), and \(\text{gd}(G)=k\). Also, for integers \(n\), \(d\), and \(k\) with \(2\leq d<n\), \(2\leq k<n\), and \(n-d-k+1\geq 0\), there exists a graph \(G\) of order \(n\), diameter \(d\), and \(\text{gd}(G)=k\). A graph \(F\) is said to be a minimum geodetic subgraph if there exists a graph \(G\) containing \(F\) as an induced subgraph such that \(V(F)\) is a minimum geodetic set for \(G\). Finally, it is shown that a nontrivial graph \(F\) is a minimum geodetic subgraph if and only if every vertex of \(F\) has eccentricity 1 or no vertex of \(F\) has eccentricity 1.