Orientations of digraphs almost preserving diameter
An orientation of a digraph \(D\) is an oriented graph \(H\) obtained by removing exactly one arc of each 2-cycle of \(D\). The authors prove that if \(D\) belongs to certain classes \(C\) of digraphs, then there exists an orientation \(H\) of \(D\) such that \(\text{diam}(H)\leq \max\{c,\text{diam}(D)\}\) where \(c\) is a constant whose value depends on the class \(C\). For example, if \(C\) is the class of strong semicomplete bipartite digraphs with at least two nodes in each partite set, then \(c=5\).
scientific article; zbMATH DE number 1792338
scientific article