pipette
ESEspañol

An improved upper bound for oriented diameter of graphs with diameter

Yaokun Feng, Hui Lei, Xiaopan Lian, Zijian Ren

Preprint

In the authors' words

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.

Main resultThe abstract does not state a limitation.

Appeared: Friday, September 25. arXiv. Preprint, not yet peer-reviewed.