On The Bounds Of Geodetic Numbers Of Graphs

For two vertices u and v of a graph G, a u-v geodesic is a shortest path between u and v. Let Iu,v denote the set of all vertices lying on a u-v geodesic. For a subset S, let I(S) denote the union of all Iu,v for u, v∈S. The geodetic set is S such that I(S)= V(G). The geodetic number g(G) of a graph G is the minimum cardinality of a set S with I(S)= V(G). For a digraph D, there is analogous terminology for the geodetic number g(D). The geodetic spectrum of G is the set S(G)={g(D):D is an oriention of G}. The upper geodetic number is g+(G)=max S(G). The purpose of this thesis is to study the bound of g+(G) and g(G) for connected graphs G. The following are the main results:In Chapter 1, the background and research progress of geodetic set are simply illustrated.In Chapter 2, we study a conjecture on the lower bound of the upper geodetic number:If G is a nontrivial connected graph of diameter d an minimum degree 5, then g+(G)≥d+δ. and we prove that it is true for triangle-free graphs, graphs withΔ≤3 and unit interval graphs.In Chapter 3, we first obtain the lower bound of the upper geodetic number of the carte-sian products of complete graph and bipartite graph. Then we investigate a conjecture on the relation between the upper geodetic number and geodetic number:For any graph G, g+(G)≥g(G). We prove that both g+(G)≥g(G) and g+(G)≥d+Δis true for the cartesian products of complete graph and tree. We also investigate the relation between g(G) and d+Δfor the cartesian products of complete graph and tree.In Chapter 4, we obtain the geodetic number of block graphs and then investigate the bound of g+(G) for block graphs.