| For a graph G, the distance between the two vertices u, v is the length of the shortest (u. v) path. For a graph G. the diameter is the maximum distance between any two vertices of G. Similarly, for a digraph D. the distance from u to v is the length of the shortest path from u to v. In addition, Charland et al. defines the strong distance sd(u. v) between two vertices u and v in a strong digraph D as the minimum size(the number of arcs)of a strong sub-digraph of D containing u and v. The strong eccentricity se(v) of a vertex v in the strong digraph D is the maximum of strong distance between v and any vertex in D. The strong diameter of the digraph D is the maximum of the strong eccentricity for any vertex in D. Similarly the strong radius of the digraph D is the minimum of the strong eccentricity for any vertex in D. With a graph G given, we will obtain the oriented graph of G after replacing each side x, y of G with arc xy or yx. If the connected graph G is strongly connected after the orientation, the orientation is called the strong orientation of G. The orientation of all the oriented graphs of G which makes the strong diameter the maximum is also called the maximum strong diameter orientation of G. It can be expressed as SDIAM(G). The orientation of all the oriented graphs of G which makes the strong diameter the minimum is also called the minimum strong diameter orientation of G. It can be expressed as sdiam(G). The strong radius orientation of G is defmed in a similar way. Many scholars have studied the diameter about the graphs and digraphs and gained a lot of results. For the digraphs, the concepts of the strong diameter and strong radius are proposed too late and the documents including the research results are few. So the further study about them is also relatively critical. In this paper, we will give the bounds of the strong diameter and the strong radius about some special digraph.This paper is composed of four chapters, the main contents as follow:In the first chapter, we simply give some useful basic concepts on graphs which will be used in the paper.In the second chapter, we introduce the present results about strong diameter and strong radius.Tn the third chapter, firstly we study a lower bound on the maximum strong diameter orientation of2-vertex multiplications of circles. The result is as follows:Let H be a circle of order n and let n≥3be an integer, and let G be2-vertex multiplications of H, then the result is SDIAM(G)≥n+2. Particularly we study the minimum strong diameter orientation of2-vertex multipli-cations of odd circles. The result is as follows:Let H be a circle of order n and let n≥3be an odd, and let G be the2-vertex multiplications of H, then sdiam(G)≤n.Secondly we study a upper bound on the minimum strong diameter orientation of2-vertex multiplication of chordal graph by adding the chords to the circle of order5. The result is as follows:Let H be the chordal graph by adding the chords to the circle of order5and let G be the2-vertex multiplications of H, then the result is sdiam(G)≤5.Then we discuss a upper bound on the minimum strong diameter orientation of2-vertex multiplication of chordal graph by adding the chords to the circle of order6. We set up the conclusion:Let H be the chordal graph by adding the chords to the circle of order6and let G be the2-vertex multiplications of H, then the result is sdiam(G)≤6.Generally, Let H be the chordal graph by adding the chords to the circle of order n and let G be the2-vertex multiplications of H, then the result is sdiam(G)≤n.In the fourth chapter, we discuss the special digraphs which has the same minimum strong diameter and minimum strong radius. The main results are as follows:(1) Let G be the2-vertex multiplication of circle of order3, then we have sdiam(G)=srad(G).(2) Let G be the2-vertex multiplication of circle of order4, then we have sdiam(G)=srad(G).(3) Let H be the chordal graph by adding chords to the circle of order4and let G be its2-vertex multiplication, then we have sdiam(G)=srad(G). |
PDF Full Text Request