Skip to content
DraconiticResearch
Search Sources API
197,787 studies31 sourcesUpdated 51 min ago
PreprintCC BY 4.0arXiv

The asymptotic maximum oriented diameter of graphs

  • Jiangdong Ai
  • Yaokun Feng
  • Hui Lei
  • Zijian Ren
Open at sourcePDFDOICite

Abstract

The oriented diameter of a connected bridgeless graph is the minimum diameter of a strong orientation. Let f(d) be the maximum oriented diameter among all such graphs of diameter d. In 1978, Chvátal and Thomassen proved f(d)≤2d2+2d and constructed graphs showing that any quadratic upper bound on f(d) must have leading coefficient at least 1/2. We prove that f(d)≤ 1/2d2+7d for every integer d≥1. This matches the leading coefficient of their lower bound and establishes f(d)=1/2d2+O(d), determining the optimal quadratic coefficient. Our proof gives a polynomial-time algorithm that constructs a strong orientation satisfying the stated bound.

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. Maximum number of spanning trees in bipartite graphs with a given diameter
    Shaohan Xu, Ivan Damnjanović, Kexiang Xu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. The diameter of recoloring graphs under a maximum average degree bound
    Ruilin Zheng, Junying Lu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Asymptotic maximum spectral radius of nonregular graphs
    Hangxi Cha, Haiying Shan
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Embracing exchange sequences and oriented matroid polyhedron diameter
    Kristóf Bérczi, Kolja Knauer, Luis Pedro Montejano +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{ai2026asymptotic,
  title = {{The asymptotic maximum oriented diameter of graphs}},
  author = {Jiangdong Ai and Yaokun Feng and Hui Lei and Zijian Ren},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.04660},
  eprint = {2610.04660},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.04660},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The asymptotic maximum oriented diameter of graphs
AU  - Jiangdong Ai
AU  - Yaokun Feng
AU  - Hui Lei
AU  - Zijian Ren
PY  - 2026
DA  - 2026/10/03
PB  - arXiv
DO  - 10.48550/arxiv.2610.04660
UR  - https://arxiv.org/abs/2610.04660
AB  - The oriented diameter of a connected bridgeless graph is the minimum diameter of a strong orientation. Let f(d) be the maximum oriented diameter among all such graphs of diameter d. In 1978, Chvátal and Thomassen proved f(d)≤2d^2+2d and constructed graphs showing that any quadratic upper bound on f(d) must have leading coefficient at least 1/2. We prove that f(d)≤ 1/2d^2+7d for every integer d≥1. This matches the leading coefficient of their lower bound and establishes f(d)=1/2d^2+O(d), determining the optimal quadratic coefficient. Our proof gives a polynomial-time algorithm that constructs a strong orientation satisfying the stated bound.
ER  -