Diameter Three Orientability of Bipartite Graphs

Abstract

In 2019, Czabarka, Dankelmann and Székely showed that for every undirected graph of order $n$, the minimum degree threshold for diameter two orientability is $\frac{n}{2}+ \Theta(\ln n)$. In this paper, we consider bipartite graphs and give a sufficient condition in terms of the minimum degree for such graphs to have oriented diameter three. We in particular prove that for balanced bipartite graphs of order $n$, the minimum degree threshold for diameter three orientability is $\frac{n}{4}+\Theta(\ln n)$.