Please use this identifier to cite or link to this item: http://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.

Page view(s)

42
checked on Sep 28, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.