Almost minimum diameter orientations of semicomplete multipartite and extended digraphs (Q1865138)

A digraph \(D\) is semicomplete if there is at least one arc between any pair of distinct vertices of \(D\). The \((s_1, s_2, \dots , s_n)\)-extension \(D(s_1, s_2, \dots , s_n)\) of a digraph \(D\) with vertices labelled \(1,2,\dots , n\) is obtained from \(D\) by replacing every vertex \(i\) by a set of \(s_i\) independent vertices. An orientation of a digraph \(D\) is a digraph obtained from \(D\) by deleting exactly one arc between \(x\) and \(y\) for every pair \(x\neq y\) of vertices such that both \(xy\) and \(yx\) are in \(D\). Almost minimum diameter orientations of certain semicomplete multipartite and extended digraphs are considered. Several generalizations of known results are proved. A survey of previous results can be found in the book of \textit{J. Bang-Jensen} and \textit{G. Gutin} [Digraphs. Theory, algorithms and applications (Springer Monographs in Mathematics, Springer, London) (2001; Zbl 0958.05002)].