An improved upper bound for oriented diameter of graphs with diameter $4$

Abstract

Let f(d) denote the smallest integer such that every bridgeless graph of diameter d admits a strong orientation with diameter at most f(d). It is known that f(2)=6 and f(3)=9. For d=4, the classical bounds of Chvátal and Thomassen [JCTB, 1978] imply 12≤ f(4)≤40, and subsequent work reduced the upper bound to 21. Very recently, Lin, Wang and You further established the substantially stronger bound f(4)≤18. Pushing this bound below $18$ turns out to be considerably more difficult, since the remaining extremal configurations cannot be handled by existing techniques based on R−S orientations and related local constructions. In this paper, we prove that f(4)≤16. 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.

An improved upper bound for the fair domination number of maximal outerplanar graphs
Yair Caro, Riste Škrekovski
arXiv19 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
An asymptotically tight bound on oriented diameter
Yaojun Chen, Jifu Lin, Xiaolin Wang +1
arXiv4 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
An asymptotically tight bound on oriented diameter
Jiangdong Ai, Yaojun Chen, Yaokun Feng +5
arXiv7 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
The asymptotic maximum oriented diameter of graphs
Jiangdong Ai, Yaokun Feng, Hui Lei +1
arXiv3 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
An improved bound on the support diameter of nonnegative planar Euler vorticity
Daomin Cao, Junhong Fan, Guodong Wang
arXiv15 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeX RIS

BibTeX

@misc{feng2026improved,
  title = {{An improved upper bound for oriented diameter of graphs with diameter $4$}},
  author = {Yaokun Feng and Hui Lei and Xiaopan Lian and Zijian Ren},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.29526},
  eprint = {2609.29526},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.29526},
}

RIS

TY  - UNPB
TI  - An improved upper bound for oriented diameter of graphs with diameter $4$
AU  - Yaokun Feng
AU  - Hui Lei
AU  - Xiaopan Lian
AU  - Zijian Ren
PY  - 2026
DA  - 2026/09/24
PB  - arXiv
DO  - 10.48550/arxiv.2609.29526
UR  - https://arxiv.org/abs/2609.29526
AB  - Let f(d) denote the smallest integer such that every bridgeless graph of diameter d admits a strong orientation with diameter at most f(d). It is known that f(2)=6 and f(3)=9. For d=4, the classical bounds of Chvátal and Thomassen [JCTB, 1978] imply 12≤ f(4)≤40, and subsequent work reduced the upper bound to 21. Very recently, Lin, Wang and You further established the substantially stronger bound f(4)≤18. Pushing this bound below $18$ turns out to be considerably more difficult, since the remaining extremal configurations cannot be handled by existing techniques based on R−S orientations and related local constructions. In this paper, we prove that f(4)≤16. 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.
ER  -

Abstract

Related

Cite