An Erdős-Pach-Pollack-Tuza theorem for oriented diameter
Source: arxiv.org/abs/2611.03169
The oriented diameter of a bridgeless graph is the minimum diameter of its strong orientations. Erdős, Pach, Pollack and Tuza proved that every connected graph of order $n$ and minimum degree $δ\ge 2$ has diameter at most $3n/(δ+1)-1$, which is sharp up to an additive constant. Cochran and Wang conjectured that the oriented diameter obeys the same bound up to an absolute additive constant. We prove this conjecture: every bridgeless graph of order $n$ and minimum degree $δ$ has a strong orientation of diameter at most $3n/(δ+1)+10^{17}$. Thus the bound of Erdős, Pach, Pollack and Tuza for the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.03169
curl -X POST /api/v1/records/arxiv/2611.03169/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.03169/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'