The Study Of Some Problems On The Geodetic Numbers Of The Graphs

The geodetic number of a graph is an important parameter revealing the structural character of graphs. The geodetic number of a graph originated from the convex set theory of geometry, topology and functional analysis, and is the generalization and application of convex set theory in graph theory; There is an important relation between the geodetic number of a graph and the problems of path covered and path decomposed.In this thesis, we will consider the geodetic number of graphs and digraphs, and research results of mine are mainly presented. The content of the thesis mainly involve the following four parts: (1) The relation between the minimum geodetic set and cut-vertices of a graph is given; (2) The geodetic numbers of the graph T_n(K_d)and T_n(C_d) are discussed; (3) Studying the geodetic number and the upper (lower) geodetic number of the graph G ∨ H; (4) The geodetic number of the graph G × P₃ is discussed.In Chapter 2, we investigate the geodetic number of undirected graph. We obtain the following results.We discuss the geodetic set of graphs containing cut-vertices, we obtain the following results: every minimum geodetic set of a graph does not contain its cut-vertices, this result is the generalization of the result on the geodetic number of T_n in [8]; In [8], Grary Chartrand, Frank Harary and Ping Zhang prove that g(K_n) = n, we show that if G is a graph with n ≥ 3 vertices and k cut-vertices, and every block of G is a complete graph, then g(G) = n- k.We define a graph T_n(H): a graph T_n(H) is a graph obtained from a tree T_n with n ≥ 2 vertices by replacing all the vertices v ∈V(T_n) and the edges uv∈ E(T_n) by E(H_u ∨ H_v), where H_u is a graph H replacing u and H_v is a graph H replacing v. And prove the following results.If T_n is a nontrivial graph with l leaves, then g(T_n(K_d)) = ld;If T_n is a star graph,then If T_n is not a star graph and T_n has l leaves, d ≥ 4 and n ≥ 3, then g(T_n(C_d)) ≤min{「d/2(?)l,2(2-l)} .In Chapter 3, we discuss the geodetic number of digraphs. The lower and upper geodetic number of G∨H and the relation between the geodetic number and the upper geodetic number of G∨ H are studied. We obtain the following results.For any two graphs G and H, we have g (G∨ H) = 2.If G and H are two nontrivial graphs, then g⁺(G∨H)≥ g⁺(G) + g⁺(H).In [1], Lu raised a conjecture that g⁺(G) ≥ g(G) for any graphs of order n withg(G) ≤ 4 or its diameter no less than (n - 1)/2. We study the relation between g⁺(G ∨H) and g(G ∨ H), and prove the following results.If neither G nor H is a complete graph then g⁺(G∨H) ≥ g(G ∨H).If H is a complete graph and G is a chordal graph or G is a graph with ω(G) < 3, then g⁺(G∨H)≥g(G∨H).Suppose that S is a minimum 2- N - dominating set of G. If every vertex of S has at most one neighbor in G/S and H is a complete graph, then g⁺(G∨H) ≥ g(G∨H).In Chapter 4, we discuss the geodetic number of cartesian product graphs. In [1], Lu raised a sufficiant and necessary condition for g(G) = g(G ×K₂), we study the geodetic number of G × H with g(H) = 2, and obtain the following results. If there exists a minimum geodetic set S and a family F based on S relatives to F can be partition into (S₁, S₂), then g(G) = g(G × H) for any graph H with g(H) = 2. If G is a nontrivial connected graph, then g(G) = g(G× P₃) if and only if there exists a minimum geodetic set S and a family F based on S such that S relatives to F can be partition...