Skip to content
DraconiticResearch
Search Sources API
182,544 studies31 sourcesUpdated 10 min ago
PreprintarXiv licencearXiv

An asymptotically tight bound on oriented diameter

  • Yaojun Chen
  • Jifu Lin
  • Xiaolin Wang
  • Ruilin Zheng
Open at sourcePDFDOICite

Abstract

Let f(d) be the smallest integer such that every connected bridgeless graph of diameter d admits an orientation with directed diameter at most f(d). Chvátal and Thomassen (1978) proved ⌈d2/2⌉+d≤ f(d) ≤ 2d2+2d. In this paper, we prove that f(d)≤ ⌈ d2/2⌉+6d, which shows f(d)= d2/2+Θ(d) and determine the leading quadratic coefficient of f(d). The key method of our proof is to construct a central subgraph H such that it admits a strong orientation of diameter O(d) and the distance between H and every vertex outside H is at most $ d/2 $.

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{chen2026asymptotically,
  title = {{An asymptotically tight bound on oriented diameter}},
  author = {Yaojun Chen and Jifu Lin and Xiaolin Wang and Ruilin Zheng},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.05061},
  eprint = {2610.05061},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.05061},
}
RIS
TY  - UNPB
TI  - An asymptotically tight bound on oriented diameter
AU  - Yaojun Chen
AU  - Jifu Lin
AU  - Xiaolin Wang
AU  - Ruilin Zheng
PY  - 2026
DA  - 2026/10/04
PB  - arXiv
DO  - 10.48550/arxiv.2610.05061
UR  - https://arxiv.org/abs/2610.05061
AB  - Let f(d) be the smallest integer such that every connected bridgeless graph of diameter d admits an orientation with directed 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 f(d)≤ ⌈ d^2/2⌉+6d, which shows f(d)= d^2/2+Θ(d) and determine the leading quadratic coefficient of f(d). The key method of our proof is to construct a central subgraph H such that it admits a strong orientation of diameter O(d) and the distance between H and every vertex outside H is at most $ d/2 $.
ER  -