OpenAlex ·
An improved upper bound for oriented diameter of graphs with diameter $4$
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.29526
- Original
- Read it at the publisher
- Topics
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\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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Boolean threshold functions, neuron capacity, and memory retrieval
Fast factorization in diagram monoids
Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7
Odd Cycle Transversal on $H$-free graphs
Construction of Partial Join Graphs with Perfect State Transfer in Shunt Decomposition-Based Quantum Walks
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.