Please use this identifier to cite or link to this item:
Title: On a conjecture concerning the orientation number of a graph
Authors: Ng, K.L. 
Keywords: Digraph
Optimal orientation
Orientation number
Issue Date: 6-Apr-2009
Citation: Ng, K.L. (2009-04-06). On a conjecture concerning the orientation number of a graph. Discrete Mathematics 309 (6) : 1603-1610. ScholarBank@NUS Repository.
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 over(d, {combining right arrow above}) (G) of G is defined by over(d, {combining right arrow above}) (G) = min {d (D) | D ∈ D (G)}. Let G (p, q ; m) denote the family of simple graphs obtained from the disjoint union of two complete graphs Kp and Kq by adding m edges linking them in an arbitrary manner. The study of the orientation numbers of graphs in G (p, q ; m) was introduced by Koh and Ng [K.M. Koh, K.L. Ng, The orientation number of two complete graphs with linkages, Discrete Math. 295 (2005) 91-106]. Define over(d, {combining right arrow above}) (m) = min {over(d, {combining right arrow above}) (G) : G ∈ G (p, q ; m)} and α = min {m : over(d, {combining right arrow above}) (m) = 2}. In this paper we prove a conjecture on α proposed by K.M. Koh and K.L. Ng in the above mentioned paper, for q ≥ p + 4. © 2008 Elsevier B.V. All rights reserved.
Source Title: Discrete Mathematics
ISSN: 0012365X
DOI: 10.1016/j.disc.2008.02.039
Appears in Collections:Staff Publications

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


checked on Nov 22, 2022


checked on Nov 22, 2022

Page view(s)

checked on Nov 24, 2022

Google ScholarTM



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