Orientations of digraphs almost preserving diameter

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. In this paper, we consider certain well-known classes of strong digraphs, each member D of which has an orientation with diameter not exceeding the diameter of D by more than a small constant.