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.