The geodetic number of an oriented graph (Q1971800)

The distance between vertices \(u\) and \(v\) in an oriented graph \(D\) is the minimum directed path length from \(u\) to \(v\), denoted by \(d(x,y)\); an \(x\)-\(y\) path of length \(d(x,y)\) is an \(x\)-\(y\) geodesic; \(I(u,v)\) denotes the set of vertices lying on a \(u\)-\(v\) geodesic or a \(v\)-\(u\) geodesic; for \(\varnothing\neq S\subseteq V(D)\), we set \(I(S)=\bigcup_{u,v\in S}I(u,v)\). \(S\subseteq V(D)\) is a geodetic set if \(I(S)=V(D)\). A geodetic set of mimumum cardinality in \(V(D)\) is a minimum geodetic set; its cardinality is \(g(D)\), the geodetic number. For a nontrivial connected undirected graph \(G\) the lower and upper orientable geodetic numbers \(g^-(G)\) and \(g^+(G)\) are respectively the minimum and maximum geodetic numbers among all orientations of \(G\). Theorem 2.5: For every connected graph \(G\) of order at least 3, we have \(g^{-1}(G)\neq g^+(G)\). Theorem 2.7: For every two integers \(n\) and \(m\) with \(1\leq n-1\leq m\leq{n\choose 2}\), there exists a connected graph \(G\) of order \(n\) and size \(m\) such that \(g^+(G)=n\). The paper closes with three problems.