The orientation number of two complete graphs with linkages

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 d→(G) of G is defined by d→(G)=min{d(D)|D∈D(G)}. In this paper, we study the orientation numbers of a family of graphs, denoted by G(p,q;m), that are obtained from the disjoint union of two complete graphs Kp and Kq by adding m edges linking them in an arbitrary manner. Define d→(m)=min{d→(G):G∈G(p,q;m)}. We prove that d→(2)=4 and min{m:d→(m)=3}=4. Let α=min{m:d→(m)=2}. We evaluate the exact value of α when p⩽q⩽p+3 and show that 2p+2⩽α⩽2p+4 for q⩾p+4.