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

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.

並列關鍵字

diameter ； orientation ； complete multipartite graph

參考文獻

[1] Boesch, F., Tindell, R.: Robbins’ theorem for mixed multigraphs. Am. Math. Mon. 87, 716-719 (1980).

[2] Chivatal, V., Thomassen, C.: Distances in orientations of graphs. J. Comb. Theory, Ser. B 24, 61-75 (1978).

[3] Gutin, G.: m-sources in complete multipartite graphs. (In Russian) Ser. Fiz-Mat. Navuk. 5, 101-106 (1989).

[4] Gutin, G.: Minimizing and maximizing the diameter in orientation of graphs. Graphs Comb. 10, 225-230 (1994).

[5] Koh, K.M., Tan, B.P.: The diameter of an orientation of a complete multipartite graph. Discrete Math. 149, 131-139 (1996).

國際替代計量

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

全文下載

主題瀏覽