The Upper and Lower Geodetic Numbers of Graphs

Abstract

For every two vertices \(u\) and \(v\) in a graph \(G\), a \(u-v\) geodesic is a shortest path between \(u\) and \(v\). Let \(I(u,v)\) denote the set of all vertices lying on a \(u-v\) geodesic. For a vertex subset \(S\), let \(I_G(S)\) denote the union of all \(I_G(u,v)\) for \(u,v \in S\). The geodetic number \(g(G)\) of a graph \(G\) is the minimum cardinality of a set \(S\) with \(I_G(S) = V(G)\). For a digraph \(D\), there is analogous terminology for the geodetic number \(g(D)\). The geodetic spectrum of a graph \(G\), denoted by \(S(G)\), is the set of geodetic numbers over all orientations of graph \(G\). The lower geodetic number is \(g^-(G) = \min S(G)\) and the upper geodetic number is \(g^+(G) = \max S(G)\). The main purpose of this paper is to investigate lower and upper geodetic numbers of graphs. Our main results in this paper are:

1. For every spanning tree \(T\) of a connected graph \(G\), \(g^-(G) \leq \ell(T)\), where \(\ell(T)\) is the number of leaves of \(T\).
2. The conjecture \(g^+(G) \geq g(G)\) is true for chordal graphs, triangle-free graphs and \(4\)-colorable graphs.