Please use this identifier to cite or link to this item:
Title: The minimum diameter of orientations of complete multipartite graphs
Authors: Koh, K.M. 
Tan, B.P. 
Issue Date: 1996
Source: 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
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)

checked on Mar 9, 2018

Google ScholarTM


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