Some Results On Geodetic Numbers Of Graphs

The concept of geodesic is originated from the convex set theory in geometry, topology, functional analysis and relativity theory. In order to research the convexity of graphs, geodetic set and geodetic number of graphs are raised. The geodetic set and geodetic number of graphs play an important role on path covering problem and decomposition of graphs, they also have significance on location problem, network design, control theory and so on.This thesis mainly investigates geodetic set and its variations, such as bound-ary geodetic set, edge geodetic set and linear geodetic set on graphs with special properties. Besides, the geodetic problems under some graphic operations are also considered. Finally, geodetic set and geodetic spectrum of oriented graphs are stud-ied.In Chapter 1, the background and research progress of geodetic set are simply illustrated.In Chapter 2, we first study some properties of geodetic set of graphs and reveal the relation between geodetic number and other parameters of graphs, such as extreme vertices number, diameter and clique number. Then, boundary geodetic sets of some graphs are given. We also study the edge geodetic number ge(G) and linear geodetic number gl(G). The following are the main results:(1) Let G be a distance-hereditary graph and does not contains K2,3 as induced subgraph. Then g(G)=gb(G).(2) Let G be a cograph with order n. Then G has a boundary geodetic set. Moreover, if G has an extreme vertex v with d(n)<6 for any u∈N(v), then g(G) = gb(G).(3) For any positive integer 2≤a≤b, there is a graph G such that g(G) = a and ge(G) = b.(4) Let T be a tree with k leaves. Then gl(T) = k and for any labeling leaves set S = {v1, v2,…, vk},S is the smallest linear geodetic set of T.In Chapter 3, we consider geodetic sets and geodetic numbers of some graphic operations. The geodetic numbers of extreme geodetic graphs are obtained. Be-sides, we investigate boundary sets, contour sets, eccentricity sets and periphery sets of strong product graphs. The main results are as follows:(1) Let G (H, respectively) be a graph of order greater than 2. If S1(S2, re-spectively) is geodetic sets of G (H, respectively), then S1×S2 be a geodetic set of G(?)H.(2) Let G (H, respectively) an extreme geodetic graph with orders greater than 2. S1 - {e11,e12,…, e1m1} (S2 = {e21, e22,…,e2m2}, respectively) be extreme ver-tices of G (H, respectively). Then g(G(?)H) = m1m2 and S1×S2 is a minimal geodetic set of G(?) H.(3) For any vertex of (g,h)∈V(G (?)H), eccG(?)H(g, h) = max{eccG(g), eccH(h)}.(4) Let G and H be two graphs. Then (?)(G(?)H) = (?)(G)×V(H)∪(?)(H)×V(G); Ct(G)×Ct(H) (?) Ct(G (?)H) (?) Ct(G)×V(H)∪Ct(H)×V(G); Ecc(G)×Ecc(H) (?) Ecc(G(?)H) (?) Ecc(G)×V(H)∪Ecc(H)×V(G): moreover, if d(G)≥d(H), then Per(G(?) H) = Per(G)×V(H).In Chapter 4, we study geodetic number and geodetic spectrum of oriented graphs and prove that the geodetic spectrum of unicyclic graphs are continuous. The results are as follows: (1)Let G(?)Cn be a unicyclic graph of order n,Then{k+1,k+2,…,n-1}(?) S(G).(2)Let G(?)Cn be a unicyclic graph of order n.Then for any positive integer k,g-(G)≤k≤g+(G),there is an oriented graph D of G,with g(D)=k.