The Upper and Lower Geodetic Numbers of Graphs.
Lin Dong, Changhong Lü, Xiao Wang · Ars Combinatoria · 2009
For any two vertices u and v in a graph G (digraph D, respectively), a u-v geodesic is a shortest path between u and v (from u to v, respectively). Let I(u, v) (ID(u, v), respectively) denote the set of all vertices lying on a u-v geodesic. For a vertex subset S, let IG(S) (ID(S), respectively) denote the union of all IG(u, v) (ID(u, v), respectively) for u, v ∈ S. The geodetic number g(G) (g(D), respectively) of a graph G (digraph D, respectively) is the minimum cardinality of a set S with IG(S) = V (G) (ID(S) = V (D), respectively). The geodetic spectrum of a graph G, denote by S(G), is the set of geodetic numbers of all orientations of graph G. The lower geodetic number is g−(G) = minS(G). 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 any connected graph G and any spanning tree T of G, g−(G) ≤ l(T ), where l(T ) is the number of leaves of T . (ii) The conjecture g+(G) ≥ g(G) is true for chordal graphs or graphs with no 3-cycle or graphs of 4-colorable.