The upper and lower geodetic numbers of graphs

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 5, let Ig{S) denote the union of all Ig(u,v) for u, v ε S. The geodetic number g(G) of a graph G is the minimum cardinality of a set S with Ig(S) = V(G). For a digraph D, there is analogous terminology for the geodetic number g(D). The geodetic spectrum of a graph G, denote by S(G), is the set of geodetic numbers over all orientations of graph G. The lower geodetic number is g^-(G) = maxS(G) and the upper geodetic number is g⁺(G) = maxS(G). The main purpose of this paper is to investigate lower and upper geodetic numbers of graphs. Our main results in this paper are: (i) For every spanning tree T of a connected graph G, g^- (G) ≤ eii;(T), where ℓ(T) is the number of leaves of T. (ii) The conjecture g ⁺(G) ≥ g(G) is true for chordal graphs, triangle-free graphs and 4-colorable graphs.