Minimum Diameter Orientations Of Two Kinds Of Graphs

The article is divided into two chapters. We chiefly study the problem on minimum diameter orientations of a graph.It is the one-way and gossip problems which lead to introduce minimum diameter orientations of a graph, namely how to change one-way street for every street of a traffic system, which every two vertices are mutually reachable and the quantity of the longest routes is minimum. Because of the wide application background, both problems are concerned and also popular today.An orientation of a graph G is a digraph obtained from G by assigning to each edge in G a direction. An orientation D of G is strong if every two vertices in D are mutually reachable in D. An edge e in a connected graph G is a bridge if G - e is disconnected. Robbins' celebrated one-way street theorem states that a connected graph G has a strong orientation if and only if no edge of G is a bridge[1]. The diameter of a graph G is finite when it has a strong orientation. How to orient G such that the diameter reaches minimum is minimum diameter orientations problem.For a bridgeless connected graph G, let (?)(G) be the family of strong orientations of G, and for any D∈(?)(G), we denote by d(D)(resp.,d(G)) the diameter of D(resp.,G). Define (?)(G) = min{d(D)|D∈(?)(G)}. G(s₁, s₂,…,s_n,) (this notation comes from [2]) is a G vertex-multiplication for any connected graph G of order n≥3 and for any sequence s_i with s_i≥2, i = 1, 2,…, n. Koh and Tay in their paper[2] give a inequality as follows: All graphs of the form G(s₁, s₂,…, s_n) are thus divided into the following three classes: At the same time Koh and Tay also give such a conjecture[2]: if G is a graph such that d(G)≥3, then G(s₁, s₂,…, s_n)(?)φ₂, (s_i≥2, i = 1, 2,…, n). It is very difficult to give a counterexample or a proof. In the first chapter we get two properties of the optimal orientations digraph for tree 2-vertex multiplications, and a method computing the diameter of 1-cycle graph. At last we'll verify that this conjecture is true for 1-cycte vertex multiplications, namely it is true when G is a 1-cycle graph.In chapter 2, we deal with minimum diameter orientations of strong products of two paths. Koh and Tay has studied minimum diameter orientations of products of path, cycle, complete graph and so on. This chapter gives minimum diameter orientations of strong products of two paths.