Almost minimum diameter orientations of semicomplete multipartite and extended digraphs

Abstract

An orientation of a digraph D is a spanning subdigraph of D obtained from D by deleting exactly one arc between x and y for every pair x ≠ 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 results on orientations of undirected graphs are obtained, some conjectures are posed.