Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.disc.2008.02.039
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
Source: 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. https://doi.org/10.1016/j.disc.2008.02.039
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
URI: http://scholarbank.nus.edu.sg/handle/10635/103670
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.

Page view(s)

17
checked on Feb 18, 2018

Google ScholarTM

Check

Altmetric


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