2025/08/25 by Boriboon, Sopon, Kittipassorn, Teeradej
#05C12 #05C20 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.17569
In 2002, Koh and Tay conjectured that every bridgeless graph of order n≥ 5 and size at least n\choose 2-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 n-d \choose 2+n+2. We prove this conjecture for the case d=n-2 and prove the lower bound of this conjecture for the case 5≤ d≤ n-2.