The orientation number of two complete graphs with linkages
type: Item
instance of: scholarly article
title: The orientation number of two complete graphs with linkages
zbMATH Open document ID: 1064.05071
author: K. L. Ng
author: K. M. Koh
published in: Discrete Mathematics
publication date: 2005-06-23T00:00:00Z
review text: Let \(F(G)\) be the family of strong orientations of a connected graph \(G\) containing no bridges. The orientation number \(N(G)\) of \(G\) is defined to be the minimum diameter for any \(D\) in \(F(G).\) Let \(H(p, q; m)\) denote a family of graphs that are obtained from the disjoint union of two complete graphs of orders \(p\) and \(q\) by adding \(m\) edges linking them in an arbitrary manner. The paper studies the orientation number of \(H(p, q; m).\) Define \(N(m)\) to be the minimum \(N(G)\) among all \(G\) in \(H(p, q; m).\) The paper is shown that \(N(2) = 4\) and \(\min\{m: N(m) = 3\} = 4.\) It also evaluates the exact value of \(\min\{m: N(m) = 2\}\) when \(q\) is restricted between \(p\) and \(p + 3\) and shows that this value is bounded between \(2p + 2\) and \(2p + 4\) for \(q > p + 3.\)
reviewed by: Wai-Kai Chen
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C78
zbMATH DE Number: 2181963
zbMATH Keywords: diameter
MaRDI profile type: Publication
full work available at URL: j.disc.2005.02.010
OpenAlex ID: W1979579415
cites work: Robbins's Theorem for Mixed Multigraphs
cites work: Q3353039
cites work: Minimizing and maximizing the diameter in orientations of graphs
cites work: Cycles and paths in semicomplete multipartite digraphs, theorems, and algorithms: a survey
cites work: The diameter of an orientation of a complete multipartite graph
cites work: The minimum diameter of orientations of complete multipartite graphs
cites work: On optimal orientations of Cartesian products of even cycles and paths
cites work: Optimal orientations of products of paths and cycles
cites work: On optimal orientations of Cartesian products of even cycles
cites work: On optimal orientations of Cartesian products of graphs. I
cites work: On optimal orientations of Cartesian products with a bipartite graph
cites work: On optimal orientations of Cartesian products of graphs. II: Complete graphs and even cycles
cites work: On optimal orientations of \(G\) vertex-multiplications
cites work: On optimal orientations of Cartesian products of trees
cites work: On a conjecture concerning optimal orientations of the Cartesian product of a triangle and an odd cycle
cites work: Diameter-preserving orientations of the torus
cites work: Orientations of the n-cube with minimum diameter
cites work: Diametrically critical tournaments
cites work: Q3754020
cites work: Every vertex a king
cites work: A Theorem on Graphs, with an Application to a Problem of Traffic Control
cites work: Q3754023
DOI: 10.1016/J.DISC.2005.02.010
description: scientific article; zbMATH DE number 2181963