A Size Condition for Small Diameter Orientable Graphs

Abstract

In 2002, Koh and Tay conjectured that every bridgeless graph of order $n\ge 5$ and size at least $\left(\genfrac{}{}{0ex}{}{n}{2}\right)-n+5$ has an orientation of diameter two. Later, Cochran, Czabarka, Dankelmann and Székely proved this conjecture and asked what is the minimum number of edges required in a bridgeless graph of order $n$ to guarantee the existence of an orientation of diameter at most $d$? We conjecture that the answer is $\left(\genfrac{}{}{0ex}{}{n-d}{2}\right)+n+2$. We prove this conjecture for the case $d=n-2$ and prove the lower bound of this conjecture for the case $5\le d\le n-2$.

11 pages, submitted