Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.disc.2005.02.010
Title: The orientation number of two complete graphs with linkages
Authors: Koh, K.M. 
Ng, K.L. 
Issue Date: 28-May-2005
Citation: Koh, K.M., Ng, K.L. (2005-05-28). The orientation number of two complete graphs with linkages. Discrete Mathematics 295 (1-3) : 91-106. ScholarBank@NUS Repository. https://doi.org/10.1016/j.disc.2005.02.010
Abstract: For a connected graph G containing no bridges, let D(G) be the family of strong orientations of G; and for any D∈D(G), we denote by d(D) the diameter of D. The orientation number d→(G) of G is defined by d→(G)=min{d(D)|D∈D(G)}. In this paper, we study the orientation numbers of a family of graphs, denoted by G(p,q;m), that are obtained from the disjoint union of two complete graphs Kp and Kq by adding m edges linking them in an arbitrary manner. Define d→(m)=min{d→(G):G∈G(p,q;m)}. We prove that d→(2)=4 and min{m:d→(m)=3}=4. Let α=min{m:d→(m)= 2}. We evaluate the exact value of α when p≤q≤p+3 and show that 2p+2≤α≤2p+4 for q≥p+4. © 2005 Elsevier B.V. All rights reserved.
Source Title: Discrete Mathematics
URI: http://scholarbank.nus.edu.sg/handle/10635/104329
ISSN: 0012365X
DOI: 10.1016/j.disc.2005.02.010
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

6
checked on Nov 26, 2022

WEB OF SCIENCETM
Citations

5
checked on Nov 18, 2022

Page view(s)

132
checked on Nov 24, 2022

Google ScholarTM

Check

Altmetric


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