論賦向完全多部圖之最小直徑

Abstract

Robbins 研究單行道問題時，證明了一個連通圖有強定向的充分必要條件是此圖中沒有橋。除了強定向的存在性之外，一個有趣且實際的問題是，這些強定向的最小直徑的長度為何? 更精確地說，對於一個給定的圖 G ，用 D(G) 表示圖 G 的所有強定向所成的集合。圖 G 的每一種定向都有一個直徑，其中最小的直徑其長度記為d(G), 是我們所要決定的目標參數。 關於完全多部圖的 d(G) 值，已知是 2 或 3 ，但是在許多情形下，還無法決定究竟是 2 還是 3 。在這篇論文中，我們決定了一些完全三部圖的 d(G) 值。此外，我們找到了 d(G) 值為 2 的一類部數大於三的完全多部圖。

On investigating the one-way street problem, Robbins proved that a connected graph has a strong orientation if and only if it has no bridges. An interesting and practical problem is that, besides the existence of a strong orientation, what is the minimum diameter of such an orientation. More precisely, for a given graph G, denote D(G) the family of all strong orientations of G. The object parameter then is d(G) = min{d(D) : D 2 D(G)}. Denote K(p1, p2, . . . , pn) the complete n-partite graph having pi vertices in the ith partite set. While it is known that 2< = d(K(p1,p2, . . . , pn)) < = 3 for n > = 3, there are still many ~d(K(p1, p2, . . . , pn)) remain un-determined. In this thesis, we establish some new results. We determine d(G) of some complete 3-partite graphs. Also, we find a family of complete multipartite graphs G with d(G)=2, for n>3.