A Size Condition for Diameter Two Orientable Graphs

Abstract

It was conjectured by Koh and Tay [Graphs Combin. 18(4) (2002), 745--756] that for $n\ge 5$ every simple graph of order $n$ and size at least $\left(\genfrac{}{}{0ex}{}{n}{2}\right)-n+5$ has an orientation of diameter two. We prove this conjecture and hence determine for every $n\ge 5$ the minimum value of $m$ such that every graph of order $n$ and size $m$ has an orientation of diameter two.