arxiv: 2605.11667 · v1 · submitted 2026-05-12 · 🧮 math.CO

Recognition: no theorem link

An improved upper bound on the oriented diameter of graphs with diameter 4

Jifu Lin, Lihua You

Pith reviewed 2026-05-13 01:02 UTC · model grok-4.3

classification 🧮 math.CO

keywords oriented diameterbridgeless graphdiameter 4strong orientationupper bound

0 comments

The pith

Every bridgeless graph with diameter 4 admits a strong orientation whose diameter is at most 18.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The quantity f(d) is the smallest number such that any bridgeless undirected graph of diameter d has some way to orient its edges into a strongly connected digraph whose longest directed path is at most f(d). Earlier results placed f(4) between 12 and 21. The paper tightens the upper end of this interval to 18 by exhibiting, for every such graph, an explicit strong orientation that meets the new bound. A reader cares because the exact value of f(4) is now known to lie in a narrower interval, and the same graphs arise in network-design problems where one wants both strong connectivity and short directed distances.

Core claim

The paper proves that f(4) ≤ 18: for every bridgeless graph G with diam(G) = 4 there exists a strong orientation of G whose diameter is at most 18.

What carries the argument

An explicit construction, via case analysis on the structure of a diameter-4 bridgeless graph, that produces a strong orientation of directed diameter 18.

Load-bearing premise

The case analysis in the proof never leaves an uncovered configuration whose every strong orientation would require directed diameter larger than 18.

What would settle it

A single bridgeless undirected graph of diameter exactly 4 in which every strong orientation has diameter at least 19.

Figures

Figures reproduced from arXiv: 2605.11667 by Jifu Lin, Lihua You.

**Figure 1.** Figure 1: R-S orientation. Lemma 2.2. ([15]) θ(w, R) ≤ 2 for every w ∈ S in an R-S orientation. 3 The Proof of Theorem 1.5 To prove the main result, we first partition the vertex set of G into several small subsets, prescribe an orientation for the edges among these subsets, and then estimate the directed distances between pairs of vertices. Let G be a bridgeless graph with d(G) = 4 and g ∗ = g ∗ (G) ∈ {4, 5}. Then … view at source ↗

**Figure 2.** Figure 2: Orientation of some edges of G. Claim 1. (i) ∂(u, v) = 1, ∂(v, u) = g ∗ − 1, ∂(w, u) = ∂(v, w) = 2 for w ∈ S2,2. (ii) [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

read the original abstract

Let $f(d)$ be the smallest value for which every bridgeless graph $G$ with diameter $d$ admits a strong orientation $\overrightarrow{G}$ such that the diameter of $\overrightarrow{G}$ is at most $f(d)$. Chv\'atal and Thomassen (1978) established general bounds for $f(d)$ which implies $f(4)\geq 12$, and proved $f(2)=6$. Kwok et al. (2010) proved that $9\leq f(3)\leq 11$. Wang and Chen (2022) determined $f(3)=9$. Babu et al. (2021) showed $f(4)\leq 21$. In this paper, we improve the upper bound of $ f(4) $ to $18$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper tightens the upper bound on f(4) from 21 to 18 with a case-by-case orientation construction for bridgeless diameter-4 graphs.

read the letter

The main takeaway is that this work improves the upper bound on f(4) from 21 down to 18. The authors show that any bridgeless graph with diameter 4 has a strong orientation whose diameter is at most 18, building directly on the construction from Babu et al. (2021) by refining how they handle distance layers, cut vertices, and bridges. They partition the graphs into structural cases and supply explicit orientations for each one that keep the directed diameter inside the new bound. That is the concrete advance here: a better explicit number rather than a new technique or a resolution of the exact value. The lower bound remains 12 from Chvátal and Thomassen, so the gap is still wide, but 18 is a measurable step past 21. The paper does a decent job laying out the cases and arguing that the orientations work inside each one. The writing is straightforward and stays focused on the combinatorial details without extra claims. The soft spot is the reliance on exhaustive case analysis. The result stands or falls on whether every possible bridgeless diameter-4 graph fits into one of their categories and whether the supplied orientation really caps the diameter at 18 in every subcase. That kind of proof is easy to get wrong in small ways, and there is no machine check or independent enumeration to back it up. Still, the approach follows the same style as the earlier papers in this line, so the risk looks manageable rather than fatal. This is a paper for people already working on oriented diameters and extremal orientation problems in graphs. If you follow f(d) or related results on strong orientations, the updated bound is worth knowing and the cases might be reusable. For anyone outside that niche it is too specialized to matter much. I would send it to peer review. The claim is specific, the method is consistent with the literature, and the community can verify the cases during refereeing. It is not a big leap but it is a legitimate tightening that deserves the time.

Referee Report

2 major / 2 minor

Summary. The manuscript claims to prove that f(4) ≤ 18, improving the previous upper bound of 21 due to Babu et al. (2021). Here f(d) is the smallest integer such that every bridgeless graph of diameter d admits a strong orientation whose oriented diameter is at most f(d). The argument proceeds by reducing an arbitrary bridgeless diameter-4 graph to a finite collection of structural cases (via distance partitions, cut vertices, and bridges) and supplying an explicit strong orientation of diameter ≤18 for each case.

Significance. If the case analysis is exhaustive and each supplied orientation indeed has diameter ≤18, the result narrows the gap between the known lower bound f(4) ≥ 12 and the upper bound. It is an incremental but concrete advance in the study of oriented diameters of bridgeless graphs.

major comments (2)

[Main proof (case analysis)] The central reduction to structural cases (distance-2 and distance-3 layers, cut vertices, and bridges) must be shown to be exhaustive; any bridgeless diameter-4 graph whose induced subgraphs on these layers fall outside the enumerated subcases would leave the universal claim unproved.
[Main proof (orientation constructions)] For each enumerated case, the supplied orientation must be verified to produce oriented diameter at most 18 on every graph belonging to that case; a single counter-example instance inside a case would falsify the bound.

minor comments (2)

[Introduction] The introduction should explicitly restate the definition of f(d) and the precise statement of the main theorem for clarity.
[References] All citations (Chvátal-Thomassen, Kwok et al., Wang-Chen, Babu et al.) should be given in full bibliographic form in the references section.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. The comments correctly identify the two pillars of the proof—the exhaustiveness of the structural case division and the verification that each supplied orientation achieves oriented diameter at most 18. We address both points below and will revise the manuscript to make these aspects fully explicit.

read point-by-point responses

Referee: [Main proof (case analysis)] The central reduction to structural cases (distance-2 and distance-3 layers, cut vertices, and bridges) must be shown to be exhaustive; any bridgeless diameter-4 graph whose induced subgraphs on these layers fall outside the enumerated subcases would leave the universal claim unproved.

Authors: We agree that a self-contained argument for exhaustiveness strengthens the paper. The reduction begins by removing all bridges (which can be oriented in both directions without increasing the oriented diameter beyond the bound for the resulting components) and then handling cut vertices by considering the blocks they separate. Within each block the distance-2 and distance-3 layers from an arbitrary vertex are examined; the possible edge sets between these layers are constrained by the global diameter-4 condition and the absence of bridges. All combinatorially feasible configurations under these constraints are listed in the manuscript. To address the referee’s concern we will insert a short lemma immediately after the case division that proves, by exhaustive enumeration of the possible layer adjacencies and cut-vertex placements, that every bridgeless diameter-4 graph belongs to one of the enumerated cases. revision: yes
Referee: [Main proof (orientation constructions)] For each enumerated case, the supplied orientation must be verified to produce oriented diameter at most 18 on every graph belonging to that case; a single counter-example instance inside a case would falsify the bound.

Authors: Each case in the manuscript is accompanied by an explicit strong orientation together with a distance argument showing that any pair of vertices is connected by a directed path of length at most 18. These arguments rely on the layer structure and the chosen orientation of intra-layer and inter-layer edges. Nevertheless, we acknowledge that the current write-up leaves some of the longest-path calculations implicit. In the revision we will expand each verification subsection with a concise table or paragraph that bounds the directed distance between every pair of layer types (e.g., distance-0 to distance-4, distance-2 to distance-3, etc.) under the given orientation, thereby confirming that the maximum is indeed 18 for every graph in the case. revision: yes

Circularity Check

0 steps flagged

No circularity: pure combinatorial existence proof

full rationale

The paper proves f(4) ≤ 18 by exhibiting explicit strong orientations of diameter at most 18 for every bridgeless graph of diameter 4, via a finite case analysis on distance partitions, bridges and cut-vertices. No parameters are fitted to data, no quantity is defined in terms of itself, and no load-bearing step reduces to a self-citation or prior ansatz of the same authors. The cited prior upper bound of 21 is external and the new construction is self-contained against the definition of oriented diameter.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard graph-theoretic definitions and the assumption that a suitable orientation construction exists; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

standard math Standard definitions of graph diameter, strong orientation, and bridgeless graphs from prior literature.
f(d) is defined using these classical notions.

pith-pipeline@v0.9.0 · 5432 in / 1194 out tokens · 51700 ms · 2026-05-13T01:02:55.682612+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

[1]

J. Babu, D. Benson and D. Rajendraprasad, Improved bounds for the oriented radius of mixed multigraphs, J. Graph Theory, 103 (4) (2023) 674–689

work page 2023
[2]

J. Babu, D. Benson, D. Rajendraprasad and S.N. Vaka, An improvement to Chv´ atal and Thomassen’s upper bound for oriented diameter, Discrete Appl. Math., 304 (2021) 432–440

work page 2021
[3]

Bau and P

S. Bau and P. Dankelmann, Diameter of orientations of graphs with given minimum degree, European J. Combin., 49 (2015) 126–133

work page 2015
[4]

Boesch and R

F. Boesch and R. Tindell, Robbins’s theorem for mixed multigraphs, Amer. Math. Monthly, 87 (1980) 716-719. 35

work page 1980
[5]

Bondy and U.S.R

J.A. Bondy and U.S.R. Murty, Graph theory with Applications, London: Macmillan, 1976

work page 1976
[6]

Chen and A

B. Chen and A. Chang, Oriented diameter of graphs with given girth and maximum degree, Discrete Math., 346 (2023) 113287

work page 2023
[7]

Chung, M.R

F.R.K. Chung, M.R. Garey and R.E. Tarjan, Strongly connected orientations of mixed multigraphs, Networks, 15 (4) (1985) 477–484

work page 1985
[8]

Chv´ atal and C

V. Chv´ atal and C. Thomassen, Distances in orientations of graphs, J. Combin. The- ory Ser. B, 24 (1978) 61–75

work page 1978
[9]

Dankelmann, Y

P. Dankelmann, Y. Guo and M. Surmacs, Oriented diameter of graphs with given maximum degree, J. Graph Theory, 88 (2018) 5–17

work page 2018
[10]

Z. Ding, H. Li and G. Sun, The oriented diameter of mixed multigraphs with diameter 2, Discrete Math., 349 (2026) 115163

work page 2026
[11]

Fomin, M

F.V. Fomin, M. Matamala, E. Prisner and I. Rapaport,AT-free graphs: Linear bounds for the oriented diameter, Discrete Appl. Math., 141 (2004) 135–148

work page 2004
[12]

Gutin, Minimizing and maximizing the diameter in orientations of graphs, Graphs Combin., 10 (1994) 225–230

G. Gutin, Minimizing and maximizing the diameter in orientations of graphs, Graphs Combin., 10 (1994) 225–230

work page 1994
[13]

Koh and E.G

K. Koh and E.G. Tay, Optimal orientations of graphs and digraphs, a survey, Graphs Combin., 18 (2002) 745–756

work page 2002
[14]

Kurz and M

S. Kurz and M. L¨ atsch, Bounds for the minimum oriented diameter, Discrete Math. Theoret. Comput. Sci., 14 (2012) 109–140

work page 2012
[15]

P.K. Kwok, Q. Liu and D.B. West, Oriented diameter of graphs with diameter 3, J. Combin. Theory Ser. B, 100 (2010) 265–274

work page 2010
[16]

H. Li, Z. Ding, J. Liu and A. Chang, Diameter three orientability of mixed bipartite graphs, Graphs Comb., 41 (5) (2025) 95

work page 2025
[17]

H. Li, Z. Ding, J. Liu, Y. Gao and S. Zhao, A note on improved bounds for the oriented radius of mixed multigraphs, J. Graph Theory, 112 (2026) 15–19. 36

work page 2026
[18]

H. Li, Z. Ding, J. Liu and H.-J. Lai, Diameter two orientability of mixed graphs, Discrete Math., 349 (1) (2026) 114732

work page 2026
[19]

Li and S

R. Li and S. Chen, The oriented diameter of a bridgeless graph with the given path Pk, Discrete Math., 348(9) (2025), 114509

work page 2025
[20]

Lin and L

J. Lin and L. You, Oriented diameter of graphs with diameter and given edge girth, arXiv:2507.23517v2, https://doi.org/10.48550/arXiv.2507.23517

work page doi:10.48550/arxiv.2507.23517
[21]

Plesn´ ık, Remarks on diameters of orientations of graphs, Acta Math

J. Plesn´ ık, Remarks on diameters of orientations of graphs, Acta Math. Univ. Come- nian., 46 (1985) 225–236

work page 1985
[22]

Robbins, A theorem on graphs, with an application to a problem of traffic control, Amer

H.E. Robbins, A theorem on graphs, with an application to a problem of traffic control, Amer. Math. Monthly, 46 (1939) 281–283

work page 1939
[23]

ˇSolt´ es, Orientations of graphs minimizing the radius or the diameter, Math

L. ˇSolt´ es, Orientations of graphs minimizing the radius or the diameter, Math. Slo- vaca, 36 (1986) 289–296

work page 1986
[24]

Surmacs, Improved bound on the oriented diameter of graphs with given minimum degree, European J

M. Surmacs, Improved bound on the oriented diameter of graphs with given minimum degree, European J. Combin., 59 (2017) 187–191

work page 2017
[25]

Wang and Y

X. Wang and Y. Chen, Optimal oriented diameter of graphs with diameter 3, J. Combin. Theory Ser. B, 155 (2022) 374–388

work page 2022
[26]

Wang and Y

X. Wang and Y. Chen, P. Dankelmann, Y. Guo, M. Surmacs, L. Volkmann, Oriented diameter of maximal outerplanar graphs, J. Graph Theory, 98 (2021) 426–444. 37

work page 2021