On the Open Geodetic Number of a Graph

Abstract

For a connected graph \(G\) of order \(n\), a set \(S \subseteq V(G)\) is a geodetic set of \(G\) if each vertex \(v \in V(G)\) lies on a \(x\)-\(y\) geodesic for some elements \(x\) and \(y\) in \(S\). The minimum cardinality of a geodetic set of \(G\) is defined as the geodetic number of \(G\), denoted by \(g(G)\). A geodetic set of cardinality \(g(G)\) is called a \(g\)-set of \(G\). A set \(S\) of vertices of a connected graph \(G\) is an open geodetic set of \(G\) if for each vertex \(v\) in \(G\), either 1) \(v\) is an extreme vertex of \(G\) and \(v\) \(\in S\) or 2) \(v\) is an internal vertex of a \(x\)-\(y\) geodesic for some \(x, y \in S\). An open geodetic set of minimum cardinality is a minimum open geodetic set and this cardinality is the open geodetic number, \(og(G)\). The open geodetic numbers of certain standard graphs are determined. Connected graphs with open geodetic number 2 are characterized. For positive integers \(r, d\) and \(l \geqslant 2\) with \(r < d \leqslant 2r\), there exists a connected graph of radius \(r\), diameter \(d\) and open geodetic number \(l\). It is proved that for a tree \(T\) of order \(n\) and diameter \(d\), \(og(T) = n - d + 1\) if and only if \(T\) is a caterpillar. Also for integers \(n, d\) and \(k\) with \(2 \leqslant d < n\), \(2 \leqslant k < n\) and \(n - d - k + 1 \geqslant 0\), there exists a graph \(G\) of order \(n\), diameter \(d\) and open geodetic number \(k\). It is also proved that \(og(G) - 2 \leqslant og(G') \leqslant og(G) + 1\), where \(G'\) is the graph obtained from \(G\) by adding a pendant edge to \(G\).