2018/08/27 by Cochran, Garner, Czabarka, Éva, Dankelmann, Peter +1 · 1 citation
#05C12 #05C20 #Combinatorics (math.CO) #FOS: Mathematics #and 05C35
paper · doi:10.48550/arxiv.1808.08996
It was conjectured by Koh and Tay [Graphs Combin. 18(4) (2002), 745--756] that for n≥ 5 every simple graph of order n and size at least \binomn2-n+5 has an orientation of diameter two. We prove this conjecture and hence determine for every n≥ 5 the minimum value of m such that every graph of order n and size m has an orientation of diameter two.