Metraipolis › archive › dc_ab8d83df3e2d

An improved upper bound for oriented diameter of graphs with diameter $4$ — arXiv:2609.29526

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.29526
License (as archived)
CC0-1.0
Archived
2026-10-08T06:40:57.151Z
SHA-256 of the archived text
7fc1111b5ff69d72f8eea3f029a2de29abc4ea18d4c0ae27dfff4fd32388125a
Stable URL of this page
https://metraipolis.com/documento/dc_ab8d83df3e2d

How to cite

An improved upper bound for oriented diameter of graphs with diameter $4$ — arXiv:2609.29526 — arXiv (en), https://arxiv.org/abs/2609.29526 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ab8d83df3e2d (Metraipolis archive dc_ab8d83df3e2d, sha256 7fc1111b5ff69d72f8eea3f029a2de29abc4ea18d4c0ae27dfff4fd32388125a)
BibTeX
@misc{dcab8d83df3e2d,
  title = {An improved upper bound for oriented diameter of graphs with diameter $4$ — arXiv:2609.29526},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.29526},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ab8d83df3e2d; sha256 7fc1111b5ff69d72f8eea3f029a2de29abc4ea18d4c0ae27dfff4fd32388125a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.29526. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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\le f(4)\le40$, and subsequent work reduced the upper bound to 21. Very recently, Lin, Wang and You further established the substantially stronger bound $f(4)\le18$. 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)\le16$. 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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-25 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.29526 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T06:02:10.053Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).