Some Problems On The Geodetic Number Of The Graphs

In this thesis, we will consider the geodetic number of graphs and digraphs. The content of the thesis mainly involve the following three parts: (1) determine the structure of the graphs with g(G) — n — 1, n — 2; (2) Prove that the conjecture is true for graphs with g(G) = 5; (3) The geodetic number of the graph T × K_n is discussed.In Chapter 2, we investigate the geodetic number of undirected graph. We obtain the following two results.In [10], Gary Chartrand, Prank Harary and Ping Zhang prove that g(G) = n if and only if G ≌ K_n. We show that: (1).the geodetic number g(G) — n — 1 if and only if G ≌ H (?) K₁, where H = K_s1∪K_s2∪...∪K_sk ( k ≥ 2 , s_i ≥ 1 i = 1,2, ... , k). (2). g(G) = n-2 if and only if G have the following conditions: â… . there are two vertices x, y such that G -{x, y} ≌ K_s1 ∪_s2 ∪... ∪ K_sk ( k ≥ 2 , s_i > 1 i = 1,2, ... , k); â…¡. when d(G) = 2, we can partition G_i in this way: G_i = X_i∪ A_i∪Y_i, where X_i = {v|v ∈ V(G_i)∩N(x), v (?) N(y)}; Y_i = {v|v ∈ V(G_i)∩N(y), v (?) N{x)}; A_i = {v|v ∈V(G_i),v ∈ N(x)∩N{y)} , if X_i ≠ (?), then |Y_i ∪ A_i| ≤ 2; if Y_i ≠ 0, then |X_i ∪ A_i| ≤ 2, and there are not two components G_i, G_j such that X_i, Y_j, X_j ∩ A_j are all not empty set, or Y_i, X_j, Y_j ∩ A_j are all not empty set. â…¢. when diam(G) = 2 and x, y are not adjacent, G exist but at most two vertices . which are the neighbors of x, y. IV. when diam(G) = 3, x and y are adjacent, and there are two components in G - {x, y} at least, respectively, every vertex in the component is neighbor of x or y; for the other components, if N(x) ∩ V(Gi)≠(?), then V(G_i) (?) N(x), it is also true for y.In Chapter 3, we discuss the geodetic number of digraphs. In [4], Changhong Lu raise a conjecture: for any graph G ,g{G) ≤ g⁺{G). He also prove that the conjecture is true for graphs with g(G) ≤ 4. Based on these results, we prove the conjecture is true for graphs with g(G) = 5.In Chapter 4, we study the geodetic number of G × K_n, and obtain the following results: If there exist l leaves on the tree T_n, we have g(T_n × K_m) = max{g(T_n), g(K_m)} =...