The orientation number of two complete graphs with linkages (Q556840)

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.\)