The geodetic number of an oriented graph

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.

Recommendations

Cites work

Cited in

(29)

This page was built for publication: The geodetic number of an oriented graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1971800)