An Erdős-Pach-Pollack-Tuza theorem for oriented diameter

Introduction

Throughout, all graphs are finite and simple unless stated otherwise; multigraphs arise only from contractions, and they are always loopless. An orientation of a graph $G$ replaces each edge by one of its two possible arcs, and it is strong if every ordered pair of vertices is joined by a directed path. A bridge is an edge of a connected graph after whose removal the graph is no longer connected, and a graph is said to be bridgeless if it is connected and contains no bridge. Robbins’ theorem [7] states that a connected graph has a strong orientation if and only if it is bridgeless. For a strong orientation $D$, we write $\operatorname{dist}_{D}(x,y)$ for the length of a shortest directed path from $x$ to $y$, and $\operatorname{diam}(D)$ for the maximum of $\operatorname{dist}_{D}(x,y)$ over all ordered pairs $(x,y)$. The oriented diameter $\overrightarrow{\operatorname{diam}}(G)$ of a bridgeless graph $G$ is the minimum of $\operatorname{diam}(D)$ over all strong orientations $D$ of $G.

The study of distances in orientations goes back to Chvátal and Thomassen [3]. Among other results, they proved that every bridgeless graph of radius $r$ has an orientation of radius at most $r^2+r$; this radius theorem is used in the last step of our proof. In this paper we bound the oriented diameter in terms of the order and the minimum degree. For undirected graphs, Erdős, Pach, Pollack and Tuza [6] showed that every connected graph of order $n$ and minimum degree $\delta\ge2$ has diameter at most $\lfloor3n/(\delta+1)\rfloor-1$, and this is sharp up to an additive constant. For orientations, Bau and Dankelmann [2] proved that every bridgeless graph $G$ of order $n$ and minimum degree $\delta$ satisfies

Surmacs [8] improved the coefficient 11 to 7, and Cochran [4] obtained a bound of the form $(6+\varepsilon)n/(\delta+1)+C_{\varepsilon}$ for every fixed $\varepsilon>0$. Recently, Cochran and Wang [5] proved that for every $\varepsilon> 0$ there is a constant $C_{\varepsilon}$ such that every bridgeless graph $G$ of order $n$ and minimum degree $\delta\ge3$ satisfies $\overrightarrow{\operatorname{diam}}(G) \le(3 + \varepsilon)n/(\delta- 2) + C_{\varepsilon}$, provided that $n$ is sufficiently large. They proposed the following conjecture.

The coefficient 3 in Conjecture 1.1 cannot be lowered, as already shown by Bau and Dankelmann [2]. Indeed, Bau and Dankelmann constructed a family of graphs with minimum degree $\delta\ge4$ in which every graph $G$ has oriented diameter at least $\frac{3n}{\delta+1} - 3$, and Cochran and Wang [5] gave another family of graphs with minimum degree $\delta\ge4$ such that every member $G$ satisfies that its oriented diameter is also at least $\frac{3n}{\delta+1} - 3$. Here we give a better construction than the previous ones. Let $G$ be a graph obtained from a cycle $C = v_1v_2 \ldots v_{3k}v_1$ by replacing $v_{3i}$ with a complete graph $K_{3i}$ on $\delta- 1$ vertices, and each vertex of $K_{3i}$ is connected to $v_{3i-1}$ and $v_{3i+1}$, where $k \ge2$, $1 \le i \le k$, $\delta\ge2$, and indices are taken modulo $3k$. Observe that $G$ is a graph of order $n = k(\delta+ 1)$ vertices and minimum degree $\delta(G) = \delta$ satisfying that $\overrightarrow{\operatorname{diam}}(G) \ge\frac{3n}{\delta+1} - 1$. Indeed, $G$ is bridgeless, and any two of the $k$ edges $v_{3i+1}v_{3i+2}$ form an edge cut, so in every strong orientation of $G$ these edges all point in the same direction around the cycle. If they point from $v_{3i+1}$ to $v_{3i+2}$, then every directed path from $v_{3i+2}$ to $v_{3i+1}$ passes in order through all $k$ cliques $K_{3j}$, using at least two edges at each of them and one edge between consecutive ones, and therefore has length at least $2k + (k - 1) = 3k - 1 = \frac{3n}{\delta+1} - 1$; the other direction is symmetric.

Our main result confirms Conjecture 1.1.

Thus the bound of Erdős, Pach, Pollack and Tuza [6] for the diameter carries over to the oriented diameter of bridgeless graphs, with only the additive constant changed. Note that this concerns the extremal bound in terms of $n$ and $\delta$; for an individual graph the oriented diameter can be much larger than the diameter. We have not tried to optimise the additive constant. We keep all constants explicit in order to make clear that the additive term depends neither on $n$ nor on $\delta$; the proof actually gives $3n/(\delta+ 1) + 3.51 \cdot10^{16}$.

We now describe the proof. Write $d = \delta+ 1$. If $P$ is a shortest path in a graph of minimum degree $\delta$, then every vertex $z$ satisfies $|N[z] \cap V(P)| \le3$, and counting incidences gives $d|V(P)| \le3|N[V(P)]|$. This is the source of the coefficient 3 in [6]. In an orientation we need two edge-disjoint paths instead of one. We grow a core, that is, a vertex set $K$ together with a strong orientation of the subgraph induced by $K$, and we keep the diameter of this orientation at most $3|N[K]|/d$. To enlarge the core towards a vertex $x$, we contract $K$ to a single vertex and choose two edge-disjoint paths from the contracted vertex to $x$ of minimum total length. Their union is a chain of cycles, and we orient every cycle with the help of short paths between its two branches. The diameter of the enlarged core then increases by at most $3m/d$ plus an absolute constant, where $m$ is the number of new vertices in the closed neighbourhood of the core.

The additive constant is absorbed by a strict gain in the counting. The incidence inequality above is close to equality only when the paths run through long sequences of cliques in which every three consecutive cliques have exactly $d$ vertices. We call such sequences exact strips, and we remove long exact strips in advance by a reduction which changes the oriented diameter by exactly the right amount. Without long exact strips, the neighbourhood count beats the incidence inequality by a fixed proportion of the length of the paths. Consequently, an extension towards a vertex whose two paths have total length greater than $3.6 \cdot10^{7}d$ costs at most $3m/d$.

After this stage, every vertex has two edge-disjoint paths to the contracted core of total length $O(d)$, but the number of remaining vertices may still be large. We then select such pairs of paths in batches. A pair that is still needed after the earlier pairs of the batch have been contracted has many new neighbours, so a batch at length $L$ contains $O(q/(dL))$ pairs, where $q$ is the number of vertices outside the closed neighbourhood of the core. Each pair forms a closed trail through the contracted root, and we orient all trails of a batch at once by random priorities; the diameter of their union is $O(L\log(1+k))$ for $k$ trails. Halving $L$ from stage to stage gives a total cost of $O(d[1+\log(1+q/d^2)])$, which is at most $3q/d$ when $q/d^2$ is large. When $q/d^2$ is bounded, a separate density bound of the form $3n/d+O(1+n/d^2)$, which preserves the core, finishes the orientation with an absolute error. For $4 \le\delta\le6$ the same stopping condition already bounds the distance to the core by an absolute constant, and the radius theorem of Chvátal and Thomassen completes the orientation. Minimum degree three requires a separate fragment count before this radius completion.

Two points need care. All paths of a batch are chosen with respect to the same root before any direction is assigned, so we never need individually chosen directions to agree on shared edges. Moreover, each vertex is charged only when it first enters the closed neighbourhood of the growing core. The choice between the two ways of finishing depends only on the graph and not on the ordered pair whose distance is estimated, so a single orientation satisfies all distance bounds.

The paper is organised as follows. Section 2 collects properties of pairs of edge-disjoint paths of minimum total length. Section 3 removes long exact strips. Section 4 proves the strict counting lemma and the extension of an oriented core for $\delta\ge4$, and Section 5 treats $\delta= 3$ and constructs the initial core. Section 6 proves the density bound, Section 7 orients batches of closed trails through one root, and Section 8 completes the proof of Theorem 1.2.

Pairs of edge-disjoint paths

We first fix notation. For a graph $G$ and a set $X \subseteq V(G)$, we write $N_G[X]$ for the set consisting of $X$ and all vertices adjacent to a vertex of $X$, and $N_G^j[X]$ for the set of vertices at distance at most $j$ from $X$; for a single vertex we omit the braces. Degrees and neighbourhoods always refer to the fixed graph indicated by the subscript, which we omit when it is clear from the context. A path has no repeated vertex, and a trail has no repeated edge but may repeat vertices. The length of a path, trail or walk is its number of edges or arcs. When a connected vertex set $K$ is contracted to a single vertex, parallel edges are kept, each with its original end in $K$, and loops are deleted. Natural logarithms are denoted by $\ln$.

A core is a nonempty vertex set $K$ together with a prescribed strong orientation of the subgraph induced by $K$; a single vertex is a core of diameter 0. When a core is enlarged, all directions prescribed inside the old core are kept. Throughout the paper the minimum-degree parameter $\delta$ is fixed before any reduction, and $d=\delta+1$. In reduced graphs we only require minimum degree at least $\delta=d-1$, and we never replace $d$ by the actual minimum degree.

Proof. Keep the prescribed orientation inside $K$ and give every other edge the direction of its physical image in $D$. For an ordered pair not wholly in $K$, choose a shortest directed path between its images in $D$. This path visits the contracted root at most once. Replace that visit, if present, by a directed path inside $K$ between the recorded ends, of length at most $\Delta_K$. If an endpoint lies in $K$, use the corresponding initial or final path inside $K$. Pairs wholly in $K$ use their prescribed routes. These choices use one fixed orientation, and give the stated bound. $\square$

We use two edge-disjoint paths of minimum total length rather than two separately chosen paths. Such pairs are standard objects in disjoint-path algorithms; see Suurballe and Tarjan [9]. The optimality conditions for minimum-cost flows [1 Chapter 9] give the following description. All edges of a multigraph are regarded as distinct physical edges, including edges with the same ends.