Some Topics For Strong Geodetic Number Of Graphs

The geodesic of a graph is originated from the convex set theory and called short-est path in Graph Theory.The study of the geodesic has an important practical and theoretical significance in the design of the universe spacecraft orbit and computer net-work,it is applied in different fields.Strong geodetic problem is a generalization of geodetic problem,this thesis focuses on strong geodetic problem.Let G be a graph.Given a vertex set S,for each pair of vertices（?）be a selected fixed shortest path between x and y.Then we set（?）,then the set S is called a strong geodetic set.The strong geodetic problem is to find a minimum strong geodetic set S of G.Clearly,the collection （?）of geodesics consists of exactly（?）paths.The cardinality of a minimum strong geodetic set is the strong geodetic number of G and denoted by sg（G）.First,we give upper and lower bounds for strong geodetic number in terms of diameter and connectivity,respectively.Then we obtain the upper and lower bounds of strong geodetic number for join and corona of two graphs.At the same time,the Nordhaus-Gaddum type results of the sum and product of the strong geodetic number of a graph G and the strong geodetic number of it’s complement （?） are studied.We provide some examples to show that the above conclusions can not be improved in a sense.Next,we show that 2≤sg（G）≤n for a connected graph G of order n.Under specified conditions,the graphs with sg（G）=n,n-1,n-k,2 are characterized,re-spectively.Moreover,the extremal problems for strong geodetic number are researched and got the value of s（n,k）,f（n,k）,g（n,k）,respectively.Finally,we obtain upper and lower bounds of sg（G H）.The strong geodetic numbers of some networks are investigated in this chapter.1.For Peterson network HP₃and HP₄,we have sg（HP₃）=4,sg（HP₄）=6.2.For Torus network,if（?）.3.For n-dimensional cube Q_n,the strong geodetic number as following:sg（Q₁）=2,sg（Q₂）=3,sg（Q₃）=4,sg（Q₄）=5.For n≥5,we obtain an upper bound of Q_n:sg（Q_n）≤2^n-5×5+1.