On the Minimum Diameter among Orientations of Complete Multipartite Graphs
Date Issued
2006
Date
2006
Author(s)
Chen, Chien-Yeh
DOI
en-US
Abstract
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.
Subjects
賦向
完全多部圖
直徑
diameter
orientation
complete multipartite graph
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-95-R93221001-1.pdf
Size
23.53 KB
Format
Adobe PDF
Checksum
(MD5):eecc231ccbd8daf608c60590347f44f7