Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/104317
Title: | The minimum diameter of orientations of complete multipartite graphs | Authors: | Koh, K.M. Tan, B.P. |
Issue Date: | 1996 | Citation: | Koh, K.M.,Tan, B.P. (1996). The minimum diameter of orientations of complete multipartite graphs. Graphs and Combinatorics 12 (1) : 333-339. ScholarBank@NUS Repository. | Abstract: | Given a graph G, let script D sign(G) be the family of strong orientations of G, and define ε(G) = min{diamD\D ∈ script D sign(G)}. A pair {p, q} of integers is called a co-pair if 1 ≤, p ≤ q ≤ [[p/2] p]. A multiset {p, q, r} of positive integers is called a co-triple if {p, q} and {p, r} are co-pairs. Let K(p1,p2,...,pn) denote the complete n-partite graph having pi vertices in the ith partite set. In this paper, we show that if {p1,p2,...,pn} can be partitioned into co-pairs when n is even, and into co-pairs and a co-triple when n is odd, then ε(K(p1,p2,...,pn)) = 2 provided that (n, p1, p2, p3, p4) ≠ (4, 1, 1, 1, 1). This substantially extends a result of Gutin [3] and a result of Koh and Tan [4]. © Springer-Verlag 1996. | Source Title: | Graphs and Combinatorics | URI: | http://scholarbank.nus.edu.sg/handle/10635/104317 | ISSN: | 09110119 |
Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.