Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 38 min ago
PreprintCC BY 4.0arXiv

An asymptotically tight bound on oriented diameter

  • Jiangdong Ai
  • Yaojun Chen
  • Yaokun Feng
  • Hui Lei
  • Jifu Lin
  • Zijian Ren
  • Xiaolin Wang
  • Ruilin Zheng
Open at sourcePDFDOICite

Abstract

Let f(d) be the smallest integer such that every finite connected bridgeless simple graph of diameter d admits a strong orientation of diameter at most f(d). Chvátal and Thomassen (1978) proved ⌈ d2/2⌉+d≤ f(d)≤2d2+2d. In this paper, we prove that ⌈ d2/2⌉+d≤ f(d)≤⌈ d2/2⌉+d+18 for every d≥2, which shows that f(d)=⌈ d2/2⌉+d+O(1) and determines both the quadratic and linear terms up to a bounded additive error. The key method of our proof is to construct a central subgraph H that admits a strong orientation of diameter O(d) and is within distance ⌊ d/2⌋ of every vertex outside it. We obtain the sharp linear coefficient by jointly estimating outside paths and their connecting paths in H at the actual attachment vertices, rebuilding H when necessary.

Related

  1. An improved upper bound for oriented diameter of graphs with diameter $4$
    Yaokun Feng, Hui Lei, Xiaopan Lian +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Asymptotically Tight Bounds for Generalized Covering Radii of Binary Primitive BCH Codes at All Higher Orders
    Zeev Vladimir Belinsky, Aryeh Lev Zabokritskiy
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  3. Embracing exchange sequences and oriented matroid polyhedron diameter
    Kristóf Bérczi, Kolja Knauer, Luis Pedro Montejano +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. The asymptotic maximum oriented diameter of graphs
    Jiangdong Ai, Yaokun Feng, Hui Lei +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. An Erdős-Pach-Pollack-Tuza theorem for oriented diameter
    Jiangdong Ai, Bin Chen, Yaokun Feng
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{ai2026asymptotically,
  title = {{An asymptotically tight bound on oriented diameter}},
  author = {Jiangdong Ai and Yaojun Chen and Yaokun Feng and Hui Lei and Jifu Lin and Zijian Ren and Xiaolin Wang and Ruilin Zheng},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.09648},
  eprint = {2610.09648},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.09648},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - An asymptotically tight bound on oriented diameter
AU  - Jiangdong Ai
AU  - Yaojun Chen
AU  - Yaokun Feng
AU  - Hui Lei
AU  - Jifu Lin
AU  - Zijian Ren
AU  - Xiaolin Wang
AU  - Ruilin Zheng
PY  - 2026
DA  - 2026/10/07
PB  - arXiv
DO  - 10.48550/arxiv.2610.09648
UR  - https://arxiv.org/abs/2610.09648
AB  - Let f(d) be the smallest integer such that every finite connected bridgeless simple graph of diameter d admits a strong orientation of diameter at most f(d). Chvátal and Thomassen (1978) proved ⌈ d^2/2⌉+d≤ f(d)≤2d^2+2d. In this paper, we prove that ⌈ d^2/2⌉+d≤ f(d)≤⌈ d^2/2⌉+d+18 for every d≥2, which shows that f(d)=⌈ d^2/2⌉+d+O(1) and determines both the quadratic and linear terms up to a bounded additive error. The key method of our proof is to construct a central subgraph H that admits a strong orientation of diameter O(d) and is within distance ⌊ d/2⌋ of every vertex outside it. We obtain the sharp linear coefficient by jointly estimating outside paths and their connecting paths in H at the actual attachment vertices, rebuilding H when necessary.
ER  -