An improved upper bound for oriented diameter of graphs with diameter
En palabras de los autores
Let denote the smallest integer such that every bridgeless graph of diameter admits a strong orientation with diameter at most . It is known that and . For , the classical bounds of Chv\'{a}tal and Thomassen [JCTB, 1978] imply , and subsequent work reduced the upper bound to 21. Very recently, Lin, Wang and You further established the substantially stronger bound . Pushing this bound below turns out to be considerably more difficult, since the remaining extremal configurations cannot be handled by existing techniques based on orientations and related local constructions. In this paper, we prove that . Our approach is entirely different from previous ones. Instead of constructing a strong orientation directly, we develop a sequential orientation framework together with auxiliary distance functions and a potential-function analysis. This enables us to control directed distances globally while avoiding the intricate case analysis required by earlier methods. We believe that the framework introduced here may be useful for studying oriented diameter problems of larger diameter.
Apareció: viernes, 25 de septiembre. arXiv. Preprint, todavía sin revisión por pares.