On a conjecture concerning the orientation number of a graph |
| |
Authors: | K.L. Ng |
| |
Affiliation: | Department of Mathematics, National University of Singapore, 2, Science Drive 2, Singapore 117543, Singapore |
| |
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 of G is defined by . 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 and . 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. |
| |
Keywords: | Digraph Optimal orientation Orientation number |
本文献已被 ScienceDirect 等数据库收录! |
|