Sascha Kurz
email: sascha.kurz@uni-bayreuth.de

Martin Laetsch
email: laetsch@zpr.uni-koeln.de

Martin Lätsch

Bounds for the minimum oriented diameter

Keywords: diameter, orientation, domination

We consider the problem of determining an orientation with minimum diameter M OD(G) of a connected and bridgeless graph G. In 2001 Fomin et al. discovered the relation M OD(G) ≤ 9γ(G) -5 between the minimum oriented diameter and the size γ(G) of a minimum dominating set. We improve their upper bound to M OD(G) ≤ 4γ(G).

Introduction

An orientation of an undirected graph G is a directed graph whose arcs correspond to assignments of directions to the edges of G. An orientation H of G is strongly connected if every two vertices in H are mutually reachable in H. An edge e in an undirected connected graph G is called a bridge if G -e is not connected. A connected graph G is bridgeless if G -e is connected for every edge e, i. e. there is no bridge in G.

Conditions when an undirected graph G admits a strongly connected orientation were determined by [START_REF] Robbins | A theorem on graphs, with an application to a problem in traffic control[END_REF]. A necessary and sufficient condition is that G is connected and bridgeless. [START_REF] Chung | Strongly connected orientations of mixed multigraphs[END_REF] provided a linear-time algorithm for testing whether a graph has a strong orientation and finding one if it does. We are interested in graphs G which have a large minimum oriented diameter M OD(G) relative to their domination numbers γ(G). To this end we set Ξ(γ) := max {M OD(G) : G a connected, bridgeless graph with γ(G) ≤ γ} .

The aim of this paper is to prove a better upper bound on Ξ(γ) in terms of the domination number γ(G).

For bridgeless connected graphs G with γ = γ(G) the previously best known result was (i) :

Theorem 1.2 (Fomin et al. (2004a))

M OD(G) ≤ Ξ(γ) ≤ 9γ -5.

Our main results are

Theorem 1.3 M OD(G) ≤ Ξ(γ) ≤ 4γ
and Conjecture 1.4

Ξ(γ) = 7γ + 1 2 .
Clearly we have that Ξ(γ) is weak monotone increasing, i. e. Ξ(γ + 1) ≥ Ξ(γ) for γ ∈ N. First we observe that we have Ξ(γ) ≥ 7γ+1 In [START_REF] Chvátal | Distances in orientations of graphs[END_REF] it was also shown that we have g(2) = 6. Examples attaining this upper bound are given by the Petersen graph and by the graph obtained from K 4 by subdividing the three edges incident to one vertex. Recently in Kwok et al. (submitted) 9 ≤ g(3) ≤ 11 was shown.

The oriented diameter is trivially greater than or equal to the diameter. Graphs achieving equality are called tight. In [START_REF] Koh | On optimal orientations of cartesian products with a bipartite graph[END_REF] some Cartesian products of graphs are shown to be tight. For n ≥ 4 the n-cubes are tight [START_REF] Mccanna | Orientations of the n-cube with minimum diameter[END_REF]. The discrete tori C n × C m which are tight are completely determined in [START_REF] König | Diameter-preserving orientations of the torus[END_REF].

The origin of this problem dates back to 1938, when [START_REF] Robbins | A theorem on graphs, with an application to a problem in traffic control[END_REF] proved that a graph G has a strongly connected orientation if and only if G has no bridge. As an application one might think of making streets of a city one-way or building a communication network with links that are reliable only in one direction.

There is a huge literature on the minimum oriented diameter for special graph classes, see e. g. [START_REF] Koh | The orientation number of two complete graphs with linkages[END_REF]; Koh and Tan (1996a,b); [START_REF] Koh | Optimal orientations of products of paths and cycles[END_REF], 2000a,b, 2001[START_REF] Koh | On optimal orientations of tree vertex-multiplications[END_REF]; [START_REF] Plesník | Remarks on diameters of orientations of graphs[END_REF].

From the algorithmic point of view the following result is known:

Theorem 1.6 [START_REF] Chvátal | Distances in orientations of graphs[END_REF]) The problem whether M OD(G) ≤ 2 is N P-hard for a given graph G.

We remark that the proof is based on a transformation to the problem whether a hypergraph of rank 3 is two-colorable.

Preliminaries

A vertex set D ⊆ V (G) of a graph G is said to be a dominating set of G if for every vertex u ∈ V (G)\D there is a vertex v ∈ D such that {u, v} ∈ E(G). The minimum cardinality of a dominating set of a graph G is denoted by γ(G). If P is a path we denote by |P | its length which equals the number of its edges. If multiple vertices are allowed we speak of a walk, i. e. by a path we mean a simple path without multiple vertices. A simple cycle C of a graph G = (V, E) is a list (v 0 , . . . , v k ) of vertices in V , where v 0 = v k , |{v 0 , . . . , v k-1 }| = k and {v i , v i+1 } ∈ E for 0 ≤ i < k. Similarly |C| denotes the length of C which equals the number of its edges and vertices. By d G (x, y) we denote the distance between vertices x and y, where we drop the subscript whenever the graph is clear from the context. As abbreviation of an edge {u, v} directed from u to v we use the notation of an arc [u, v]. For further standard graph-theoretic terminology we refer the reader to [START_REF] Diestel | Graph theory[END_REF].

Our strategy to prove bounds on Ξ(γ) is to apply some transformations on connected and bridgeless graphs attaining Ξ(γ) to obtain some structural results. Instead of considering graphs G from now on we will always consider pairs (G, D), where D is a dominating set of G.

Definition 2.1 For a graph G and a dominating set D of G we call {u, v} ⊆ V (G)\D an isolated triangle if there exists a w ∈ D such that all neighbors of u and v are contained in {u, v, w} and {u, v} ∈ E(G). We say that the isolated triangle is associated with w ∈ D.

The graph on the left hand side of Figure 2 depicts an isolated triangle which is associated with u i . Definition 2.2 A pair (G, D) is in standard form if

(1) G = (V, E) is a simple connected graph without a bridge,

(2) D is both an independent set and a minimum dominating set of G,

(3) each vertex u ∈ V \D has a unique neighbor f (u) in D, (4) G is edge-minimal, meaning one cannot delete an edge in G without creating a bridge, destroying the connectivity or destroying the property of D being a dominating set, and

(5) for |D| = γ(G) ≥ 2 every vertex in D is associated with exactly one isolated triangle and for |D| = γ(G) = 1 the vertex in D is associated with exactly two isolated triangles.

Lemma 2.3 Ξ(γ) = max {M OD(G) : |D| ≤ γ, (G, D) is in standard form} .

Proof: For a given γ ∈ N we start with a connected, bridgeless graph G 1 attaining Ξ(γ) = M OD(G 1 ) and minimum domination number γ(G 1 ). Let D be an arbitrary minimum dominating set of G 1 . Our aim is to apply some graph transformations to (G 1 , D) to obtain a pair

(G 5 , D) in standard form fulfilling M OD(G 5 ) ≥ M OD(G 1 ). At the start condition (1) is satisfied for (G 1 , D). For each edge {d 1 , d 2 } in G 1 with d 1 , d 2 ∈ D we replace the path (d 1 , d 2 ) by the path (d 1 , u 1 , u 2 , d 2 )
, where u 1 , u 2 are new vertices, see the following picture: 2

Let G be a connected and bridgeless undirected graph, D be a dominating set of G and H be a strongly connected orientation of G. By diam i (H, D) we denote

max d H (u, v) : {u, v} ∩ (V (H)\D) = i .
Clearly we have diam(H) = max diam 0 (H, D), diam 1 (H, D), diam 2 (H, D) . Now we refine a lemma from [START_REF] Fomin | Bilateral orientations and domination[END_REF]:

Lemma 2.4 Let G and G be connected, bridgeless graphs such that G is a subgraph of G and D is a dominating set of both G and G. Then for every strongly connected orientation H of G there is an orientation

H of G such that diam(H ) ≤ max diam 0 (H, D) + 4, diam 1 (H, D) + 2, diam 2 (H, D) .
Proof: (We rephrase most of the proof from [START_REF] Fomin | Bilateral orientations and domination[END_REF].) We adopt the direction of the edges from H to H . For the remaining edges we consider connected components Q of G \V (G) and direct some edges having ends in Q as follows.

If Q consists of one vertex x then x is adjacent to at least one vertex u in D and to another vertex v = u (the graph G is bridgeless and D is a dominating set). If also v is an element of D then we direct one edge from x and the second edge towards x. Otherwise v is in V \D and we direct the edges {x, u}, {v, x} according to the direction of {f (v), v}: If {f (v), v} is directed towards v then we direct {x, u} from x and {v, x} towards x. Otherwise we use the opposite direction for both edges. If there are more edges incident with x (in both cases) we direct them arbitrarily. Then, we have assured the existence of vertices

u , v ∈ D such that d H (x, v ) ≤ 1 and d H (u , x) ≤ 2 or the other way round, i. e. d H (x, v ) ≤ 2 and d H (u , x) ≤ 1.
Suppose that there are at least two vertices in the connected component Q. Choose a spanning tree T in this component rooted in a vertex v. We orient edges of this tree as follows: If a vertex x of the tree has odd distance from v, then we orient all the tree edges incident to x towards x and all edges between x and V (G) from x outwards. If a vertex x of the tree has even distance from v, then we orient all edges between x and V (G) towards x, see Figure 1 in [START_REF] Fomin | Bilateral orientations and domination[END_REF]. The rest of the edges in the connected component Q are oriented arbitrarily.

In such an orientation H , for every vertex x ∈ Q there are vertices u, v ∈ D such that d H (x, v) ≤ 2 and d H (u, x) ≤ 2. Therefore, for every x, y ∈ V (G ) the distance between x and y in H is at most

max diam 0 (H, D) + 4, diam 1 (H, D) + 2, diam 2 (H, D) .
2

Due to the isolated triangles being associated with the vertices of the dominating set D, for every pair (G , D) in standard form, there exists an orientation H of G such that

M OD(G ) = diam(H ) = max diam 0 (H, D) + 4, diam 1 (H, D) + 2, diam 2 (H, D) .
(1)

If we say that H is a minimal orientation of (G , D) we mean an orientation that satisfies Equation (1). [START_REF] Fomin | Bilateral orientations and domination[END_REF] described a nice construction to obtain such a subgraph G for a given connected, bridgeless graph G fulfilling |V (G)| ≤ 5•γ (G )-4. Although their analysis contains a gap as mentioned in the introduction, we can utilize their construction for our proof.

Construction 2.5 For γ (G ) = 1 we may simply choose the single vertex in D as our subgraph G. Now we assume |D| = γ(G ) ≥ 2. Iteratively, we construct a tree T k for k = 1, . . . , |D|. The tree T 1 consists of one vertex x 1 in D. To construct T k+1 from T k we find a vertex x k+1 in D\V (T k ) with minimum distance to T k . The tree T k+1 is the union of T k with a shortest path from x k+1 to T k . Since D is a dominating set this path has length at most 3. We say that the edges of this path are associated with x k+1 . At the last step we obtain a dominating tree T with D ⊆ T and with |V (T )| ≤ 2(|D| -1) + |D|.

In order to transform T into a connected and bridgeless graph we construct a sequence of subgraphs G k for k = 1, . . . , |D|. We say that x j ∈ D is fixed in G k if no edge associated with x j is a bridge in G k . Notice that x 1 is fixed in T because it does not have any associated edge.

We set G 1 = T . Assume we have constructed the subgraph G k . If x k+1 is already fixed in G k we set G k+1 = G k . If x k+1 is not fixed in G k we add a subgraph to G k to obtain G k+1 . Let P k be the path added to T k to obtain T k+1 and e ∈ P k be the bridge in G k whose vertices have maximum distance to x k+1 . By removing e we obtain two connected subgraphs H and H . Next we choose a shortest path R in G -e connecting H with H and add R to G k . Since D ⊆ V (T ) and D is a dominating set, R has length at most three. By repeating this step for the at most two remaining bridges in P k we obtain a subgraph G k+1 where x k+1 is fixed.

By using an arbitrary strongly connected orientation of G and by showing |V (G |D| )| ≤ ∆(γ) in Construction 2.5 for a function ∆ : N → N one can conclude M OD(G) ≤ ∆(γ) + 4 -1 using Lemma 2.4, since a shortest path does contain every vertex at most once. ∆(γ) = 5 • γ -4 seems to be best possible, see [START_REF] Fomin | Bilateral orientations and domination[END_REF] and Figure 4. With Lemma 2.4 in mind we would like to restrict our investigations to connected, bridgeless subgraphs containing the dominating set.

Definition 2.6 For a pair (G , D) in standard form we call G a minimal subgraph of (G , D), if

(1) D is a dominating set for G,

(2) G is a connected and bridgeless subgraph of G , and

(3) G is vertex and edge-minimal with respect to properties (1) and (2). For γ(G) = 2 we may assume

D = {d 1 , d 2 }. Since d G (d 1 , d 2 ) = 3 there is a path (d 1 , v 1 , v 2 , d 2 ) in G. Let (d 1 , u 1 , . . . , u r , d 2 ) be a shortest path from d 1 to d 2 in G := G -{v 1 , v 2 } . From considering the f (u i ) we conclude r = 2. If {v 1 , v 2 } ∩ {u 1 , u 2 } = ∅,
then the graph on the left-hand side of Figure 4 is a minimal subgraph of G. Otherwise we assume u 1 = v 1 and u 2 = v 2 . Now let (d 1 , w 1 , . . . , w r , d 2 ) be a shortest path from

d 1 to d 2 in G := G -{d 1 , v 1 } . Due to the minimality we have f (w r-1 ) = d 1 . If w r-1 = v 1 then either {v 1 , v 2 } ∩ {w r-1 , w r } = ∅ or {v 1 , u 2 } ∩ {w r-1 , w r } = ∅,
so that the graph on the left-hand side of Figure 4 is a minimal subgraph of G. In the remaining case we have w r-1 = v 1 and vertex w r-2 is a neighbor of w r-1 and d 1 . Thus the graph on the right-hand side of Figure 4 is a minimal subgraph of G.

Thus, up to symmetry, there are two possible minimal subgraphs for γ(G) = 2 given in Figure 4. By H we denote the depicted corresponding orientation of the edges. Since in both cases we have diam 0 (H, D) ≤ 4 and diam 1 (H, D), diam 2 (H, D) ≤ 5 we can apply Lemma 2.4 to obtain the stated result.

2

Lemma 2.8 Ξ(3) = 11.

Proof:

The third example from Figure 1 yields Ξ(3) ≥ 11. Construction 2.5 allows us to explicitly construct a finite list of possible subgraphs G for γ = 3. We can assume that these graphs G are minimal subgraphs of a suitable pair (G , D) in standard form and so we can drop all graphs which are not minimal (during the construction). Doing this we obtain a list of non-isomorphic minimal subgraphs. Since this case differentiation is a bit laborious, but not difficult, we outsource it to Section B in the appendix. In Figure 5

Reductions

In this section we will propose some reductions for critical minimal subgraphs G of pairs (G , D) in standard form, in order to provide some tools for an inductive proof of Theorem 1.3. Additional reductions which might be useful in an induction proof of Conjecture 1.4 are delayed to Section A in the appendix.

Lemma 3.1 Let G be a critical minimal subgraph of (G , D) in standard form with γ = γ (G ) = |D| ≥ 3, x a vertex contained in the dominating set D, and Proof: Let Ci be the induced subgraphs of

C 1 , . . . , C r the connected components of G -x. If r ≥ 2, then we have Ξ(γ) ≤ max Ξ(γ + 1 -i) + Ξ(i) -4 : 2 ≤ i ≤ γ -1 . x h h h h h h x x T T E E c ' ' T T d d s x h h x h h x h h T T T E d d c c ' ' h h x h h x h h x T T E c c ' d d © d d s x h h h x h h h x T T E E c c ' ' d d d d x h h h x h x h h T T E E c ' ' ' c x h h x h h h h x T E E c ' d d s E c d d s ' T h h h x x h h h x T E E c ' T E c ' d d s c x h h x h h h h x T E E ' d d s E c ' T c c h h x h h x h h x T E c ' ' E T © E c d d s x h x h x h h h h T E E E c ' T c ' © d d s x h h h x h h h x h T E E E E c ' T © d d s c ' T h x h h h x x h h T T d d s d d s © © E E d d c T h x h h h x h x h c ' ' c E c E d d s © d d s h h x x h h h h x h E T ' T E c ' T E © T E © h x h h h h x h h x c ' d d s T E d d E c © ' h x h h h h x h h x c ' d d s T E d d E c c ' ' h h x x h h h h x h ' T T E c c E E c ' T © h h x h x h h h x h ' T T ' d d E c E T c ' E © h h x h x h h x h T T E E E E E c c ' x h x h h h h h x T E T E c ' ' ' T © d d h h x h h x x h h h h T E E c ' ' ' ' ' c d d x h h x h h x h h h h ' ' ' ' ' E T T d d d d d d © h h x h h x x h h h h T E E c ' ' ' ' ' T d d d d x h h x h h x h h h h ' ' ' E E E T d d d d d d s d d s c © h h x h h x x h h h h T E E c ' ' ' ' ' E d d x h h x h h x h h h h ' ' ' E E E c d d d d s d d s c ©
V (C i ) ∪ {x} in G. We set D i = {x} ∪ (V (C i ) ∩ D) and γ i := |D i |-1 so that we have 1+ i γ i = γ.
Since G is a minimal subgraph we have γ i ≥ 1 for all i. Now we choose arbitrary minimal orientations Hi of the Ci . Thus we have diam 0 ( Hi + 1) -2, anddiam 2 ( Hi , D i ) ≤ Ξ(γ i + 1) for all i. Since Ci and Cj are edge-disjoint for i = j we can construct an orientation H of G by taking the directions of the Hi . Now we analyze the distance

, D i ) ≤ Ξ(γ i + 1) -4, diam 1 ( Hi , D i ) ≤ Ξ(γ i
d H (u, v) in H for all pairs u, v ∈ V (G). If u and v are contained in the same component Ci we have d H (u, v) = d Hi (u, v). If u is contained in Ci and v is contained in Cj , then we have d H (u, v) ≤ d Hi (u, x) + d Hj (x, v). Since x ∈ D we have diam 2 (H, D) ≤ max diam 2 ( Hi , D i ), diam 1 ( Hi , D i ) + diam 1 ( Hj , D j ) : i = j ≤ max Ξ(γ i + 1), Ξ(γ i + 1) + Ξ(γ j + 1) -4 : i = j diam 1 (H, D) ≤ max diam 1 ( Hi , D i ), diam 1 ( Hi , D i ) + diam 0 ( Hj , D j ) : i = j ≤ max Ξ(γ i + 1) -2, Ξ(γ i + 1) + Ξ(γ j + 1) -6 : i = j , and diam 0 (H, D) ≤ max diam 0 ( Hi , D i ) + diam 0 ( Hj , D j ) : i = j ≤ max Ξ(γ i + 1) + Ξ(γ j + 1) -8 : i = j . From 1 + r i=1 γ i = γ we conclude γ i ≤ γ -2. Combining this with Ξ(n -1) ≤ Ξ(n) yields the stated upper bound. 2 Lemma 3.2 Let G be a critical minimal subgraph of (G , D) in standard form with γ = γ(G ) = |D| ≥ 3, x a vertex not contained in the dominating set D, and C 1 , . . . , C r the connected components of G -x. If either r ≥ 3 or r = 2 and |D ∩ V (C 1 )| ≥ 2, where f (x) ∈ C 1 , we have Ξ(γ) ≤ max Ξ(i) + Ξ(γ + 1 -i) -4 : 2 ≤ i ≤ γ -1 . Proof: W.l.o.g. let f (x) be contained in C 1 . Let C1 be the induced subgraph of V (C 1 ) ∪ {x} in G and D 1 = D ∩ V (C 1 ). For i ≥ 2 let Ci be the induced subgraph of V (C i ) ∪ {x} in G with additional vertices y i , z i , additional edges {x, y i }, {x, z i }, {y i , z i }, and D i = (V (C i ) ∩ D) ∪ {z i }. We set γ 1 = |D 1 | ≥ 1 and γ i = |D i | -1 ≥ 1 for i ≥ 2 so that we have i γ i = γ.
By Hi we denote a minimal orientation of Ci . W.l.o.g. we assume that in H1 the edge {f (x), x} is directed from f (x) to x and that for i ≥ 2 in Hi the edges {x, y i }, {x, z i }, {y i , z i } are directed from x to y i , from y i to z i and from z i to x. Due to the minimality of the orientations Hi we have diam 0 ( H1

, D 1 ) ≤ Ξ(γ 1 ) -4, diam 1 ( H1 , D 1 ) ≤ Ξ(γ 1 ) -2, diam 2 ( H1 , D 1 ) ≤ Ξ(γ 1 ), and for i ≥ 2 we have diam 0 ( Hi , D i ) ≤ Ξ(γ i + 1) -4, diam 1 ( Hi , D i ) ≤ Ξ(γ i + 1) -2, diam 2 ( Hi , D i ) ≤ Ξ(γ i + 1).
We construct an orientation H of G by taking the directions of the common edges with the Hi . Now we analyze the distance d H (u, v) in H for all pairs u, v ∈ V (G). We only have to consider the cases where u and v are in different connected components. Let us first assume u ∈ Ci , v ∈ Cj with i, j ≥ 2. We have

d H (u, v) ≤ d Hi (u, x) + d Hj (x, v) ≤ d Hi (u, z i ) -2 + d Hj (z j , v) -1, since every directed path from a vertex u ∈ V (G) to z i in Hi uses the arcs [x, y i ], [y i , z i ],
and every directed path from z j to a vertex v ∈ V (G) in Hj uses the arc [z j , x]. Now let u be in C1 and v be in Ci with i ≥ 2. Since the edge {f (x), x} is directed from f (x) to x, both in H and in H1 , we can conclude

d H (u, v) ≤ d H1 (u, x) + d Hi (x, v) ≤ d H1 (u, f (x)) + 1 + d Hi (z i , v) -1. If u ∈ Ci with i ≥ 2 and v ∈ C1 , then we similarly conclude d H (u, v) ≤ d Hi (u, x) + d H1 (x, v) ≤ d Hi (u, z i ) -2 + d H1 (x, v). Thus using Ξ(i -1) ≤ Ξ(i) for i ∈ N, γ i ≤ γ -2 for i ≥ 2, and γ i + γ j ≤ γ -1 for all i = j in total we have diam 2 (H, D) ≤ max diam 2 ( H1 , D 1 ), diam 2 ( Hi , D i ), diam 1 ( Hi , D i ) + diam 1 ( Hj , D j ) -3, diam 1 ( H1 , D 1 ) + diam 1 ( Hi , D i ), diam 2 ( H1 , D 1 ) + diam 1 ( Hi , D i ) -2 ≤ max Ξ(γ -1), Ξ(γ i + 1) + Ξ(γ j + 1) -7, Ξ(γ 1 ) + Ξ(γ i + 1) -4 : 2 ≤ i < j ≤ max Ξ(i) + Ξ(γ + 1 -i) -4 : 2 ≤ i ≤ γ -1 diam 1 (H, D) ≤ max diam 1 ( H1 , D 1 ), diam 1 ( Hi , D i ), diam 0 ( Hi , D i ) + diam 1 ( Hj , D j ) -3, diam 0 ( H1 , D 1 ) + diam 1 ( Hi , D i ), diam 1 ( H1 , D 1 ) + diam 0 ( Hi , D i ), diam 2 ( H1 , D 1 ) + diam 0 ( Hi , D i ) -2, diam 1 H1 , D 1 + diam 1 Hi , D i -2 ≤ max Ξ(γ -1) -2, Ξ(γ i +1) + Ξ(γ j +1) -9, Ξ(γ 1 ) + Ξ(γ i +1) -6 : 2 ≤ i < j ≤ max Ξ(i) + Ξ(γ + 1 -i) -6 : 2 ≤ i ≤ γ -1 diam 0 (H, D) ≤ max diam 0 ( H1 , D 1 ), diam 0 ( Hi , D i ), diam 0 ( Hi , D i ) + diam 0 ( Hj , D j ) -3, diam 0 ( H1 , D 1 ) + diam 0 ( Hi , D i ), diam 1 ( H1 , D 1 ) + diam 0 ( Hi , D i ) -2 ≤ max Ξ(γ -1) -4, Ξ(γ i +1) + Ξ(γ j +1) -11, Ξ(γ 1 ) + Ξ(γ i +1) -8 : 2 ≤ i < j ≤ max Ξ(i) + Ξ(γ + 1 -i) -8 : 2 ≤ i ≤ γ -1 , which yields Ξ(γ) ≤ max Ξ(i) + Ξ(γ + 1 -i) -4 : 2 ≤ i ≤ γ -1 . 2 y i i i i y f (x) x z w y 1 y 2 d d d d d d i i i y x z y 1 y 2 d d d s y i i i i y f (x) x z w y 1 y 2 E © d d s d d © d d s
components C 1 , C 2 with D ∩ V (C 1 ) = f (x) and there exist y 1 = y 2 ∈ V (G)\D with f (y 1 ) = f (y 2 ) = f (x) and {x, y 1 }, {x, y 2 } ∈ E(G) then we have Ξ(γ) ≤ Ξ(γ -1) + 4.
Proof: Since G is a minimal subgraph, we have V (C 1 ) = {f (x), w} and the neighbors of f (x) and w in G are contained in {f (x), w, x}. As an abbreviation we set f (y 1 ) = f (y 2 ) = z ∈ D. See the drawing on the left hand side in Figure 6 for a graphical representation of this situation. Now we consider the subgraph C2 consisting of the induced subgraph of V (C 2 ) ∪ {x} with the additional edge {x, f (y 1 )}. Let H 2 be a minimal orientation of C2 , where we assume that the edge {z, y 1 } is directed from z to y 1 , see the middle graph of Figure 6. Now we construct an orientation H of G by taking the directions from H 2 and redirecting some edges. We direct the edges from x to w, from w to f (x), from f (x) to x, from x to y 1 , from y 1 to z, from z to y 2 , and from y 2 to x, as depicted in the right drawing of Figure 6. Now we analyze the distance d H (a, b) between two vertices in V (G). If a and b are both in C2 , then we can consider a shortest path P in H 2 . It may happen that P uses some of the redirected edges {x, y 1 }, {y 1 , z}, {z, y 2 }, {y 2 , x} or the missing edge {x, z}. In this case P contains at least two vertices from {x, y 1 , y 2 , z}. If P uses more than two vertices from {x, y 1 , y 2 , z} then we only consider those two vertices which have the largest distance on P . Looking at our redirected edges in H we see that the distance between two such vertices is at most three while deleting at least one edge of P , so that we have

d H (a, b) ≤ d H2 (a, b) + 2 in this case. Now let b be in C2 . In H we have d H (f (x), z) ≤ 3 due to the path (f (x), x, y 1 , z). Since d H (z, y 2 ) = 1 we have d H (f (x), b) ≤ d H2 (z, b) + 3. Similarly we obtain d H (w, b) ≤ d H2 (z, b) + 4. With D 2 = D\{f (x)} the set D 2 is a dominating set of C2 and we can check that |D 2 | = γ( C2 ). Since z ∈ D 2 and H 2 is a minimal orientation, for b 1 ∈ D 2 , b 2 / ∈ D 2 we have d H2 (z, b 1 ) ≤ Ξ(γ -1) -4 and d H2 (z, b 2 ) ≤ Ξ(γ -1)-2 yielding d H (f (x), b 1 ) ≤ Ξ(γ -1), d H (f (x), b 2 ) ≤ Ξ(γ -1)+2, d H (w, b 1 ) ≤ Ξ(γ -1)+1, and d H (w, b 2 ) ≤ Ξ(γ -1) + 3. This is compatible with Ξ(γ) ≤ Ξ(γ -1) + 4 due to f (x), b 1 ∈ D and w, b 2 /
∈ D. Now let a be in C2 . We consider a shortest path P in H 2 from a to z. In H we have d H (z, f (x)) ≤ 4 by considering the path (z, y 2 , x, w, f (x)). Since P cannot use an arc from y 1 to z (this arc is directed in the opposite direction in H 2 ) either P contains a vertex in {x, y 2 } or P also exists in H, so that we have d H (a, f (x)) ≤ d H2 (a, z) + 4. Similarly we obtain d H (a, w) ≤ d H2 (a, z) + 3. Since H 2 is a minimal orientation we conclude similarly as in the above paragraph that all distances are compatible with Ξ(γ) ≤ Ξ(γ -1) + 4. 2

Lemma 3.4 Let G be a minimal subgraph of a pair (G , D) in standard form. If there exist

z 1 , z 2 ∈ V (G)\D with f (z 1 ) = f (z 2 ) and {z 1 , z 2 } ∈ E(G), then either z 1 or z 2 is a cut vertex.
Proof: If z 1 has no other neighbors besides z 2 and x := f (z 1 ) then either z 2 is a cut vertex or z 1 can be deleted from G without destroying the properties of Definition 2.6. We assume that neither z 1 nor z 2 is a cut vertex. Thus both z 1 and z 2 have further neighbors y 1 and y 2 , respectively. Since {z 1 , z 2 } cannot be deleted we have y 1 = y 2 . Let P 1 be a shortest path from y 1 to z 2 in G\{z 1 }. Since {z 1 , z 2 } cannot be deleted P 1 contains the edge {x, z 2 }. Similarly there exists a shortest path from y 2 to z 1 containing the edge {x, z 1 }. Thus the existence of P 1 and P 2 implies that {z 1 , z 2 } could be deleted, which is a contradiction to the minimality of G. 2

So far we have presented reduction techniques for almost all cases of cut vertices in minimal subgraphs G of a pair (G , D) in standard form. The remaining cases are rather special. So let x be a cut vertex of G. If we cannot apply neither Lemma 3.1 nor Lemma 3.2 then G -x decomposes into two connected components C 1 , C 2 with D ∩ C 1 = f (x). As shown in the proof of Lemma 3.3 we have |V (C 1 )| = 2 due to the minimality of G. For the second vertex in C 1 , besides f (x), we introduce the notation t(x) and remark that all edges being incident in G with vertices of V (C 1 ) are given by {x, f (x)}, {f (x), t(x)}, and {t(x), x}. For brevity we call such a vertex x a special cut vertex.

y i i i i y E c c d d s d d s x 1 x 2 f (x 1 ) f (x 2 ) t(x 1 ) t(x 2 ) i y i E E x 1 z x 2
Lemma 3.5 Let G be a critical minimal subgraph of (G , D) in standard form with γ = γ(G ) = |D| ≥ 3. If x 1 and x 2 are two adjacent special cut vertices in G then we have Ξ(γ) ≤ Ξ(γ -1) + 4.

Proof: We construct a graph G from G by deleting the vertices in I := {f (x 1 ), t(x 1 ), f (x 2 ), t(x 2 )} together with their incident edges, and inserting a new dominating vertex z into the edge {x 1 , x 2 }, see Figure 7. Let D = D ∪ {z}\{f (x 1 ), f (x 2 )} and H be a minimal orientation of G, where we assume that the edges {x 1 , z}, {z, x 2 } are directed from x 1 to z and from z to x 2 . Since the size of the dominating set decreases by one, i. e.

| D| = |D| -1, we have diam 2 ( H, D) ≤ Ξ(γ -1), diam 1 ( H, D) ≤ Ξ(γ -1) -2,
and diam 0 ( H, D) ≤ Ξ(γ -1) -4. Next we construct an orientation H of G by keeping the directions of all common edges with H, directing the edge {x 1 , x 2 } from x 1 to x 2 , and for i = 1, 2 directing the six remaining edges from x i to f (x i ), from f (x i ) to t(x i ), and from t(x i ) to x i . Now we analyze the distances in H. Let a, b be two arbitrary vertices in V (G)\I and a i be a vertex in {f (x i ), t(x i )} for i = 1, 2. With this we have

d H (a, b) ≤ d H (a, b) d H (a 1 , a 2 ) ≤ 5 d H (f (x 2 ), f (x 1 )) ≤ 2 + d H (z, x 1 ) -1 + 1 d H (f (x 2 ), t(x 1 )) ≤ 2 + d H (z, x 1 ) -1 + 2 d H (t(x 2 ), f (x 1 )) ≤ 1 + d H (z, x 1 ) -1 + 1 d H (t(x 2 ), t(x 1 )) ≤ 1 + d H (z, x 1 ) -1 + 2 d H (a 1 , a) ≤ 2 + d H (z, a) d H (a 2 , a) ≤ 2 + d H (z, a) -1 d H (a, a 1 ) ≤ d H (a, z) -1 + 2 d H (a, a 2 ) ≤ d H (a, z) + 2, resulting in diam i (H, D) ≤ diam i ( H, D) + 4 for i = 0, 1, 2. 2
4 Proof of the main theorem

In this section we want to prove Theorem 1.3. We use induction on γ(G) and minimal counter examples with respect to γ(G).

.3) (G, G , D) each triangle Y in G is given by V (Y ) = {x, f (x), t(x)}
, where x is a special cut vertex.

Proof: Let Y be a triangle in G with vertex set {u, v, w}. Since (G , D) is in standard form at most one of these three vertices is a dominating vertex. If one of these three vertices, say u, is a dominating vertex, then we can apply Lemma 3.4 and deduce that either v or w is a special cut vertex using the fact that we cannot apply Lemma 3.2.

In the remaining cases we have {u, v, w} ∩ D = ∅. If f (u) = f (v) then edge {u, v} can be deleted without creating a bridge, which contradicts the minimality of G. Thus f (u), f (v), f (w) are pairwise distinct and we consider shortest paths P 1 from f (u) to f (v) and P 2 from f (u) to f (w) in G -u. Since at least one of the paths P 1 or P 2 does not contain the edge {v, w} we can either delete {u, v} or {u, w} without creating a bridge, which contradicts the minimality of G.

2 z j j z j j z z j j j j E E E T T T ' ' ' c c c v 0 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 v 11 z j j j z j j z j j j j z j z j z j j E E E E T T ' ' ' c ' T d d d ' T d d d T E © E T © v 8 v 9 v 0 v 1 v 2 v 3 w 8 z 8 w 7 z 7 v 4 z 2 w 2 v 7 v 6 v 5 z 6 w 6
.3) (G, G , D) there is no simple cycle C = (v 0 , . . . , v 3k = v 0 ) in G with k ≥ 2 and v 3j ∈ D for all 0 ≤ j < k.
Proof: We assume the existence of such a cycle C, see the graph on the left hand side in Figure 8 for an example, and consider another graph G arising from G by:

(1) deleting the edges of C,

(2) deleting the vertices v 3j for 0 < j < k,

(3) inserting vertices u j and edges {v 0 , v j }, {v 0 , u j }, {u j , v j } for all 0 < j < 3k with 3 j, and by (4) identifying all vertices v 3j ∈ G with the vertex v 0 ∈ G, meaning that we replace edges {v 3j , x} in G, where x / ∈ C, by edges {v 0 , x} in G.

We remark that this construction does not produce multiple edges since (G , D) is in standard form. The

This yields

diam 2 (H, D) ≤ max diam 2 ( H, D) + 3k -2, diam 1 ( H, D) + 3k -1, 3k -1 ≤ 4 • |D| -k + 2 ≤ 4 • |D| diam 1 (H, D) ≤ max diam 1 ( H, D) + 3k -2, diam 0 ( H, D) + 3k -1, 3k -1 ≤ 4 • |D| -k ≤ 4 • |D| -2 diam 0 (H, D) ≤ max diam 0 ( H, D) + 3k -2, 3k -3 ≤ 4 • |D| -k -2 ≤ 4 • |D| -4 2 Lemma 4.4 For a minimal counter example (to Theorem 1.3) (G, G , D) there is no simple cycle C = (v 0 , . . . , v l = v 0 ) in G with |V (C) ∩ D| ≥ 2 and for each v j ∈ V (C)\D we have f (v j ) ∈ V (C) or v j is a cut vertex in G.
Proof: To the contrary let C be such a cycle of minimal length. W.l.o.g. we can assume v 0 ∈ D. Since (G , D) is in standard form we conclude l ≥ 6 from k := |V (C) ∩ D| ≥ 2. Due to the minimality of

C we have f (v j ) ∈ {v j-1 , v j+1 } for each vertex v j ∈ V (C)\D satisfying f (v j ) ∈ V (C). Thus C is chordless since G is a minimal subgraph.
By y we denote the number of vertices v j in V (C) with v j / ∈ D and f (v j ) / ∈ V (C) and by Y the corresponding set. We remark that all elements of Y are special cut vertices. For each v j ∈ Y we set z j = f (v j ) / ∈ V (C) and denote the unique common neighbor t(v j ) of v j and z j by (1) deleting the edges of C,

w j ∈ V (G)\(V (
(2) deleting the vertices {z j , w j : 0

< j < l} ∪ (V (C) ∩ D) \{v 0 },
(3) inserting vertices u j and edges {v 0 , v j }, {v 0 , u j }, {u j , v j } for all 0 < j < l with v j / ∈ D, and by ( 4) identifying all vertices v j ∈ D with the vertex v 0 ∈ G, meaning that we replace edges {v j , x} in G by edges {v 0 , x} in G.

We remark that this construction does not produce multiple edges since (G , D) is in standard form. The set

D := D\{v 1 , . . . , v l-1 , z 1 , . . . , z l-1 } is a dominating set of G with | D| = |D| -k -y + 1.
Let H be a minimal orientation of ( G, D). We construct an orientation H of G by keeping the directions of all common edges with H and by orienting the edges of C from v j to v j+1 . The missing edges {v j , z j }, {z j , w j }, and {w j , v j } are oriented from v j to z j , from z j to w j , and from w j to v j , see the graph on the right hand side of Figure 8. For brevity we set A := V (C) ∪ {w j , z j : 0 < j < l}.

Now we analyze the distances in H. Thus for

|D| ≥ k + y + 1, k ≥ 2, y ≥ 1 we have diam 2 (H, D) ≤ max diam 2 ( H, D) + 3k + y -2, diam 1 ( H, D) + 3k + y, 3k + y + 3 ≤ 4 • |D| -k -3y + 3 ≤ 4 • |D| diam 1 (H, D) ≤ max diam 1 ( H, D) + 3k + y, diam 0 ( H, D) + 3k + y, 3k + y + 3 ≤ 4 • |D| -k -3y + 3 ≤ 4 • |D| -2 diam 0 (H, D) ≤ max diam 0 ( H, D) + 3k + y, 3k + y + 3 ≤ 4 • |D| -k -3y ≤ 4 • |D| -4.
deleting the edge {v i , v i+1 } in T and adding path P yields a backbone tree. Otherwise deleting vertex v i+1 with its two incident edges from T and adding path P yields a backbone tree. In both cases we have |V (T )| > V (T ), which contradicts the maximality of T . 2

In order to bound |V (G)| for a minimal subgraph G from above we perform a technical trick and count the number of vertices of a different graph Ĝ arising from G as follows. We label the special cut vertices of G by v 1 , . . . , v m and set D = D ∪ {v i : 1 ≤ i ≤ m} \{f (v i ) : 1 ≤ i ≤ m}. Next we delete the vertices in {f (v i ), t(v i ) : 1 ≤ i ≤ m} and their incident edges from G. We replace each edge {v i , x} by a pair of two edges {v i , y x,vi }, {y x,vi , x}, where the y x,vi are new vertices, i. e. we insert a new vertex into each such edge. Assuming that we cannot apply Lemma 3.5, the distance between vertices in D is at least three. (In general we could require that the edges are subdivided for each special vertex, so that an original vertex can be subdivided several times. This would result in a graph where the distance between vertices in D is always at least three.) With this we have | D| = |D|, |V ( Ĝ)| ≥ |V (G)|, the set D is a dominating set of Ĝ, and Ĝ is a subgraph of a suitable pair in standard form. If Ĝ would not be a minimal subgraph then also G would not be a minimal subgraph. In the sequel the symbol f refers to the new "domination" function in Ĝ instead of G. We will call this graph transformation the construction. An example is given in Figure 9. Due to Lemma 4.2 for each minimal counter example (G, G , D) to Theorem 1.3 the graph Ĝ does not contain a triangle. Since a backbone tree T of a minimal subgraph G is a subgraph of G, we can apply the hat-construction from above to obtain a tree T , see Figure 10. Lemma 4.8 For each backbone tree T of a minimal subgraph G of (G , D) in standard form, T is a backbone tree of Ĝ. If T is maximum then so is T .

j z j j j j z j z j z j E E E T T ' ' c T E © E T © v 7 v 0 v 1 v 2 v 3 v 4 z 2 w 2 v 6 v 5 z 6 w 6 G z j j z j j z j j z j j v 0 v 1 y v1,v2 v 2 v 6 y v5,v6 v 5 v 4 E E E T T T ' ' ' c c c y v3,v2 v 3 y v7,v6
Proof: We perform the hat-construction step-by-step for each special cut vertex x ∈ V (G). We remark that f (x) is a leaf in T with unique neighbor x since t(x) cannot be contained in T . T arises from T by deleting f (x) and subdividing every edge in T -f (x) which is adjacent to x. For D = D ∪ {x}\{f (x)} we have that D is a dominating set and D ⊆ V ( T ). Clearly T is a tree without leafs in V ( T )\ D and containing all edges {v, f (v)} where v ∈ V ( T )\ D. Reversing the hat-construction yields the maximality of T . 2

Similar as in Lemma 4.7 we show that each edge of Ĝ has at least one vertex in T :

j z j j j z z j z v 0 v 1 v 2 v 3 v 4 z 2 v 6 v 5 z 6 T z j j z j j z j j z v 0 v 1 y v1,v2 v 2 v 6 y v5,v6 v 5 v 4 y v3,v2
v 3 T Fig. 10: An example for the construction of T from a backbone tree T .

Lemma 4.9 Let (G, G , D) be a minimal counter example to Theorem 1.3 and T be a maximum backbone tree of Ĝ with respect to its dominating set D. Then for every edge {u, v} ∈ E( Ĝ) we have {u, v} ∩ V ( T ) = ∅.

Proof: Suppose to the contrary that there is an edge {u, v} ∈ E( Ĝ) with {u, v} ∩ V ( T ) = ∅. Adding the path P = (f (u), u, v, f (v)) to T yields a cycle C = (v 0 , . . . , v l-1 ) containing f (u), u, v, and f (v). Since Ĝ does not contain a triangle we have f (u) = f (v). Using the same argument as in the proof of Lemma 4.7 we conclude that there does not exist an index i with v i-1 , v i , v i+1 / ∈ D, where the indices are read modulo l, i. e. v -1 = v l-1 and v l = v 0 .

The cardinality of D C := V (C) ∩ D is at least two. Since we cannot apply Lemma 4.4 or Lemma 3.5 D C contains exactly one vertex which does not correspond to a special cut vertex in G and one vertex, say v 2 , which does correspond to a special cut vertex s in G, i. e. we have |D C | = 2 and l = 6. Since v 2 corresponds to a special cut vertex in G the vertices v 1 and v 3 arise during the hat-construction while subdividing incident edges of s. Thus in G we have the edges {v 2 , v 0 }, {v 2 , v 4 } and f (v 0 ) = f (v 4 ) = v 5 = f (v 2 ) so that we can apply Lemma 3.3 and finally end up in a contradiction.

2

Proof of Theorem 1.3: Let (G, G , D) be a minimal counter example to Theorem 1.3 and T be a maximum backbone tree of G. We will show that we have |V (G)| ≤ 4•(|D|-1)+1, which is sufficient for our claim due to the following consideration. The diameter of an arbitrary strongly connected orientation H of G is at most 4 • (|D| -1) since a shortest path uses every vertex at most once. By applying Lemma 2.4 we conclude M OD(G

) ≤ 4 • |D| = 4 • γ(G ).
For this purpose we apply the hat-construction to G, T and obtain another minimal subgraph Ĝ with maximum backbone tree T . As mentioned before we have

|V ( Ĝ)| ≥ |V (G)| so that it is sufficient to show |V ( Ĝ)| ≤ 4 • (| D| -1) + 1 = 4 • (|D| -1) + 1. For brevity we set k := |D|.
Obviously there exists a sequence T 1 , . . . , T k of trees which are subgraphs of T satisfying |V (T i ) ∩ D| = i, |V (T 1 )| = 1, and T k = T . Similar as in Construction 2.5 we denote the unique vertex of T 1 by x 1 and for 2 ≤ i ≤ k we denote the unique vertex of V (T i )\V (T i-1 ) ∩ D by x i . The tree T i+1 is the union of T i with a path P i from x i+1 to T i of length 2 or 3. The edges in P i are called associated with x i+1 . Reusing the idea of Construction 2.5 we construct a sequence of graphs G 1 , . . . , G k containing T as a subgraph. We say that x j is fixed in G i if no edge associated with x j is a bridge in G i . So finally G k is a bridgeless connected subgraph of Ĝ containing all vertices in D. Via induction we prove

|V (G i )\V (T i )| ≤ i -1 so that we have |V (G k )| ≤ |V (T k )| + |V (G k )\V (T k )| ≤ (3k -2) + (k -1) = 4(k -1) + 1.
We set G 1 = T . Assume that we have constructed the subgraph G i . If x i+1 is already fixed in G i we set G i+1 = G i . Otherwise we consider the path P i = (x i+1 , v 2 , v 1 , . . . ), where v 2 , v 1 / ∈ D. To simplify things we introduce the path P i := x i+1 , v 2 , v 1 , f (v 1 ) . Either P i = P i or P i = P i -f (v 1 ).

Suppose that e 1 := { f (v 1 ), v 1 } is a bridge in G i . Deleting e 1 from G i yields two connected components C 1 , C 2 where we assume that x i+1 ∈ V (C 2 ). If there is a path R 1 in Ĝ -e 1 connecting C 1 with a vertex from V (C 2 )\{v 1 , v 2 } without using the vertices v 1 or v 2 , then adding the path R 1 to G i yields a graph G i+1 where x i+1 is fixed. Due to Lemma 4.9 the path R 1 contributes at most one extra vertex. So let us assume that no such path R 1 exists. Suppose there is a path R 2 in Ĝ -e 1 connecting C 1 with v 2 without using vertex v 1 . As special cut vertices do not exist in Ĝ and we cannot use one of the previous reduction lemmas v 2 cannot be a cut vertex. Since Ĝ is bridgeless connected there exists a path R 2 in Ĝ -e 1 connecting v 1 with C 2 without using v 2 . From the existence of R 2 and R 2 we conclude that deleting the edge {v 1 , v 2 } does not produce a bridge in Ĝ, which contradicts the minimality of Ĝ. So let us further assume that neither such a path R 1 nor such a path R 2 exists. In this situation all paths in Ĝ -e 1 connecting C 1 with C 2 end in v 1 so that v 1 should be a cut vertex, which is not possible. So in all cases where e 1 is a bridge we can construct G i+1 having the desired properties.

Next suppose that e 1 is not a bridge but e 2 := {v 1 , v 2 } is a bridge in G i . If there is a path R 1 in Ĝ -e 2 connecting C 1 with a vertex from V (C 2 )\{v 2 } without using vertex v 2 , then adding the path R 1 to G i yields a graph G i+1 where x i+1 is fixed. Due to Lemma 4.9 the path R 1 contributes at most one extra vertex. So let us assume that no such path R 1 exists. In this situation all paths in Ĝ -e 2 connecting C 1 with C 2 end in v 2 so that v 2 should be a cut vertex, which is not possible.

The last remaining possibility is that only the edge e 3 := {v 2 , x i+1 } is a bridge in G i . Since Ĝ is bridgeless connected there is a path R connecting C 1 with C 2 in Ĝ -e 3 such that appending R yields a graph G i+1 where x i+1 is fixed. Due to Lemma 4.9 the path R 1 contributes at most one extra vertex.

Thus the sequence of graphs G 1 , . . . , G k exists and G k is a minimal subgraph. So either G k = Ĝ or Ĝ is not a minimal subgraph.

2

We would like to remark that our reduction technique is constructive in the following sense: If we have a graph G and a dominating set D, not necessarily a minimum dominating set of G, then we can construct an orientation H of G in polynomial time satisfying diam(H) ≤ 4 • |D|: First we apply the transformations of the proof of Lemma 2.3 to obtain a graph G, which satisfies conditions (1), ( 3)-( 6) of Definition 2.2 and where D remains a dominating set. In the following we will demonstrate how to obtain an orientation H of G satisfying diam( H) ≤ 4 • |D|. From such an orientation we can clearly reconstruct an orientation H of G. Since Lemma 2.4 does not use the minimality of the dominating set D we can restrict our consideration on a minimal subgraph Ġ of G. Since neither Lemma 4.3, Lemma 4.4 nor one of the lemmas in Section 3 uses the minimality of the domination set D, we can apply all these reduction steps on Ġ. These steps can easily be reversed afterwards. If no reduction step can be applied then either we ended up with a graph whose dominating set consists of at most two vertices or the graph has so few vertices that we can use an arbitrary strongly connected orientation due to the proof of Theorem 1.3. By reversing all previous steps we obtain the desired orientation and remark that all steps can be performed in polynomial time.

Conclusion and outlook

In this article we have proven

M OD(G) ≤ 4 • γ(G)
for all connected, bridgeless graphs and conjecture

M OD(G) ≤ 7γ(G) + 1 2
to be the true upper bound. Lemma 2.8 shows that Theorem 1.3 is not tight for γ = 3. Some of our reduction steps in Section 3 can also be used for a proof of Conjecture 1.4. Key ingredients might be the lemmas 4.3 and 4.4, which can be utilized as reductions for Conjecture 1.4 if k +y is large enough. Figure 5 indicates several cases which cannot be reduced so far. Besides a proof of Conjecture 1.4 one might consider special subclasses of general graphs to obtain stronger bounds on the minimum oriented diameter. E. g. for C 3 -free graphs and C 4 -free graphs we conjecture that the minimum oriented diameter is at most 3 • γ + c for a suitable constant c.

A Reductions being compatible with Conjecture 1.4

We have some hope that it is possible to prove Conjecture 1.4 using a similar approach as in Section 3 while including some new ideas and a more sophisticated analysis. To this end we give some reductions which are compatible with Conjecture 1.4. For γ = 2 there are only two possible subgraphs, see Figure 4, which might occur as building bricks for critical minimal subgraphs.

Lemma A.1 Let G be a critical minimal subgraph of (G , D) in standard form with γ = γ(G ) = |D| ≥ 3. If G contains vertices x, y ∈ D, l 1 , l 2 , r 1 , r 2 ∈ V (G)\D, two edge disjoint paths P 1 = (x, l 1 , r 1 , y), P 2 = (x, l 2 ,
r 2 , y), all neighbors of l 1 , r 1 are in {x, l 1 , r 1 , y}, and all neighbors of l 2 , r 2 are in {x, l 2 , r 2 , y}, then we have Ξ(γ) ≤ Ξ(γ -1) + 3.

Proof: Let G be the graph which arises from G by deleting l 1 , l 2 , r 1 , r 2 and identifying x with y. Now let D := D\{y} and H be an arbitrary minimal orientation of G. Thus we have diam 0 ( H, D) ≤ Ξ(γ -1) -4, diam 1 ( H, D) ≤ Ξ(γ -1) -2, and diam 2 ( H, D) ≤ Ξ(γ -1). We construct an orientation H of G by directing the two paths P 1 and P 2 in opposite directions, and by taking the directions from H. Now we analyze the distance d H (u, v) in H for all pairs u, v ∈ V (G). If both u and v are in

I := {l 1 , l 2 , r 1 , r 2 }, then we have d H (u, v) ≤ 5 ≤ Ξ(γ -1) + 3. If none of u and v is in I, then we have d H (u, v) ≤ d H (u, v) + 3. In the remaining cases we have |{u, v} ∩ I| = 1. For u ∈ I, v / ∈ I we have d H (u, v) ≤ d H (x, v) + 5. Similarly, for u / ∈ I, v ∈ I we have d H (u, v) ≤ d H (u, x) + 5. Thus we obtain diam 2 (H, D) ≤ max diam 2 ( H, D) + 3, diam 1 ( H, D) + 5, 5 ≤ Ξ(γ -1) + 3, diam 1 (H, D) ≤ max diam 1 ( H, D) + 3, diam 0 ( H, D) + 5, 5 ≤ Ξ(γ -1) + 1, and
diam 0 (H, D) ≤ diam 0 ( H, D) + 3 ≤ Ξ(γ -1) -1, yielding Ξ(γ) ≤ Ξ(γ -1) + 3. 2
We remark that Lemma A.1 applies to a graph containing the graph on the left hand side of Figure 4 as an induced subgraph, where the vertices depicted by empty circles have no further neighbors in the whole graph.

Lemma A.2 Let G be a critical minimal subgraph of (G , D) in standard form with γ = γ(G ) = |D| ≥ 3. If G contains vertices x, y, z ∈ D, four edge disjoint but not necessarily vertex disjoint walks W 1 = (x, v 1 , v 2 , v 3 , y), W 2 = (y, v 4 , v 5 , v 6 , z), W 3 = (x, u 1 , u 2 , y), W 4 = (y, u 3 , u 4 , z)
, and all edges being incident to vertices in

I := {v 1 , v 2 , v 3 , v 4 , v 5 , v 6 , u 1 , u 2 , u 3 , u 4 } are contained in the union of the edge sets E(W 1 ) ∪ E(W 2 ) ∪ E(W 3 ) ∪ E(W 4 ), then we have Ξ(γ) ≤ Ξ(γ -2) + 7.
Proof: First we want to determine some structure information on the vertices v i , u j and the incident edges. We have

f (v 1 ) = f (u 1 ) = x, f (v 3 ) = f (v 4 ) = f (u 2 ) = f (u 3 ) = y, f (v 6 ) = f (u 4 ) = z, and f (v 2 ), f (v 5 ) ∈ {x, y, z}. Additionally we have |{u 1 , u 2 , u 3 , u 4 , v 1 , v 3 , v 4 , v 6 }| = 8
. Indeed we will prove |I| = 8. Using the minimality of G we can determine the possibilities for v 2 and v 5 depending on their f -values.

(a) f (v 2 ) = x: If v 2 = u 1 then G -v 1 would also be bridgeless connected, which is a contradiction to the minimality of G. Thus we have v 2 = u 1 in this case.

Proof: We can rephrase most of the proof of Lemma 3.2.

Using γ i + γ j ≤ γ -1 for all i = j, Ξ(i -1) ≤ Ξ(i) and γ i ≤ γ -2 for i ∈ N yields diam 2 (H, D) ≤ max Ξ(γ -1), Ξ(γ i + 1) + Ξ(γ j + 1) -7, Ξ(γ 1 ) + Ξ(γ i + 1) -4 : 2 ≤ i < j ≤ max Ξ(i) + Ξ(γ + 1 -i) -7, Ξ(i -1) + Ξ(γ + 1 -i) -4 : 2 ≤ i ≤ γ -1 diam 1 (H, D) ≤ max Ξ(γ -1) -2, Ξ(γ i + 1) + Ξ(γ j + 1) -9, Ξ(γ 1 ) + Ξ(γ i + 1) -6 : 2 ≤ i < j ≤ max Ξ(i) + Ξ(γ + 1 -i) -9, Ξ(i -1) + Ξ(γ + 1 -i) -6 : 2 ≤ i ≤ γ -1 diam 0 (H, D) ≤ max Ξ(γ -1) -4, Ξ(γ i +1) + Ξ(γ j +1) -11, Ξ(γ 1 ) + Ξ(γ i +1) -8 : 2 ≤ i < j ≤ max Ξ(i) + Ξ(γ + 1 -i) -11, Ξ(i -1) + Ξ(γ + 1 -i) -8 : 2 ≤ i ≤ γ -1 , so that Ξ(γ) ≤ max Ξ(i) + Ξ(γ + 1 -i) -7, Ξ(i -1) + Ξ(γ + 1 -i) -4 : 2 ≤ i ≤ γ -1 . 2
We would like to remark that Lemma 4.3 become compatible with Conjecture 1.4 if the size of the cycle is large enough. By slightly adjusting the estimations in the last lines of the proof of Lemma 4.3 one sees that k ≥ 3 is already sufficient.

Similarly there is also a reduction based on the idea of Lemma 4.4 which is compatible with Conjecture 1.4. For this purpose one has to require the special structure of the small components S arising by deleting a cut vertex on the cycle. In its current form the estimations are too weak for some subcases so that the adopted statement should become compatible with Conjecture 1.4 only for relatively large l, e. g. k + y ≥ 17 should definitely work. On the other hand we are quite sure that the analysis could be refined so that the reduction works also for smaller values of l and larger connected components S.

B Minimal subgraphs for γ = 3

In this section we outline how the 25 non-isomorphic minimal subgraphs G for γ = 3, see Figure 5, can be obtained along the lines of Construction 2.5.

First we start to consider the trees T k from Construction 2.5, where we assume w.l.o.g. that T k is a maximum backbone tree. As G has to contain two dominating vertices at distance three we can assume w.l.o.g. that T 2 is a path of length three. For T 3 there are only two possible cases up to symmetry, see Figure 11. The next steps are to construct all possible graphs G 1 and G 2 , where the dominating vertices are fixed. So let us assume that T 3 is given by the graph on the left hand side of Figure 11 and call it type 1. Deleting the edge {v 1 , v 2 } results in two connected subtrees and we consider a shortest path P connecting vertex v 1 with V (T 3 )\{v 1 } in G -{v 1 , v 2 }. Due to the proof of Lemma 4.7 P has either length two or length three. In the latter case appending P to T 3 produces a simple cycle satisfying the requirements of Lemma 4.3. W.l.o.g. we assume that the end vertex of P in V (T 3 ) -{v 1 } is given by v i , where the index i is maximal with this property. The entire list of possible cases is depicted in Figure 12.

v f f v f f v v 7 v 6 v 5 v 4 v 3 v 2 v 1 v f f f v v v 1 v 2 v 4 v 6 v 3 v 5 ¡ ¡ e e
v f f v f f v f y 1 d d [1] v f f v f f v f y 1 d d [2] v f f v f f v f f y 1 y 2 d d [3] v f f v f f v f y 1 f f f f f [4] v f f v f f v f y 1 g g g g g g g [5] v f f v f f v f f y 1 y 2 g g g g g g g [6]
Fig. 12: Fixing v2 for a maximum backbone tree of type 1.

Next we consider all possible extensions of case [5] in Figure 12. Since deleting the edge {v 7 , v 6 } produces two connected components with vertex sets {v 7 } and {v 1 , . . . , v 6 } there is a connecting path P in G -{v 6 , v 7 }. Let us denote the at most two new vertices of P by y 3 and y 4 . Due to the minimality of G several cases cannot occur. For the path (v 7 , y 3 , v 5 ) the edge {v 5 , v 6 } becomes redundant, for the path (v 7 , y 3 , y 4 , v 4 ) vertex v 5 and its incident edges become redundant, and for the path (v 7 , y 3 , y 4 , v 1 ) vertex y 1 and its incident edges become redundant. The remaining three cases are depicted in Figure 13. Suitable orientations, with respect to Lemma 2.8, are given in Figure 5. Next we consider all possible extensions of case [4] in Figure 12. Since deleting the edge {v 7 , v 6 } produces two connected components with vertex sets {v 7 } and {v 1 , . . . , v 6 } there is a connecting path P in G -{v 6 , v 7 }. Let us denote the at most two new vertices of P by y 3 and y 4 . The possibility P = (v 7 , y 3 , y 1 ) contradicts the minimality of G since the edge {v 5 , y 1 } could be deleted without creating a bridge. Also the possibility P = (v 7 , y 3 , y 4 , v 1 ) contradicts the minimality of G since the vertex y 1 with its incident edges could be deleted without creating a bridge. The remaining cases are depicted in Figure 14. We remark that the graph on the right hand side of Figure 14 is isomorphic to the graph in the middle of Figure 13. Suitable orientations, with respect to Lemma 2.8, for the three graphs in the middle of Figure 14 are given in Figure 5.

[4.1] v f f v f f v f f f f f f f y 3 v f f v f f v f f f f f f f d d y 3 v f f v f f v f f f f f f f f d d y 4 y 3 v f f v f f v f f f f f f f f f f f f y 3 v f f v f f v f f f f f f f g g g g g g g y 3
Fig. 14: (Almost) fixing v7 for a maximum backbone tree of type 1 in case [4].

It remains to extend the graph on the left hand side of Figure 14. Here we can assume that vertex v 7 has no additional neighbor due to the minimality of G. Deleting the edge {v 5 , v 6 } produces two connected components so that there is a connecting path P in G -{v 5 , v 6 }. There is no edge {y 3 , x} with x ∈ {y 1 , v 2 , v 3 , v 5 } since otherwise the edge {y 3 , v 6 } would be redundant. Next we conclude that vertex y 3 does not have an additional neighbor y 5 / ∈ {y 1 , v 1 , . . . , v 7 }. Otherwise the edge {y 3 , v 6 } would be redundant due to the edge {f (y 5 ), y 5 } ∈ E(G). So we can assume that the connecting path P starts with v 6 . For paths of length 1 we have the possibilities P = (v 6 , v 2 ) and P = (v 6 , v 3 ), see the two graphs on the right hand side of Figure 15. It remains to consider the cases where P has length two. Here we have a neighbor y 5 of v 6 with f (y 5 ) ∈ {v 1 , v 4 }. If f (y 5 ) = v 1 then vertex y 1 can be deleted without creating a bridge, which is a contradiction to the minimality of G. If f (y 5 ) = v 4 then we obtain the bridgeless connected minimal subgraph drawn in Figure 15. Since there obviously exists an orientation H of G with diam 0 (H, D) ≤ 7 and diam 1 (H, D), diam 2 (H, D) ≤ 9, see Figure 5, all minimal subgraphs arising as extensions of case [4] do not contradict Lemma 2.8.

Next we consider all possible extensions of case [3] in Figure 12. Deleting the edge {v 4 , v 5 } produces two connected components, so that there is a connecting path P in G -{v 4 , v 5 }. Let us denote the at most two new vertices of P by y 3 and y 4 . Since we have exhaustively treated the cases [4], [5], and [6], we can assume that P is not given by (v 1 , y 3 , v 5 ), (v 1 , y 3 , v 6 ), or (v 1 , y 3 , y 4 , v 7 ). Thus the first vertex of P is not given by v 1 .

If P starts with one of the vertices v 2 , v 3 , y 1 , or y 2 , then we can assume, due to symmetry, that the path starts either with v 2 or with v 3 . Let us first consider paths of length one, i. e. we add an edge. If we add the edge {v 2 , v 5 } or the edge {v 2 , v 6 } we could delete vertex v 3 with its incident edges, without creating a bridge, which is a contradiction to the minimality of G. Adding the edge {v 3 , v 5 } or {v 3 , v 6 } yields the cases [3.6] and [3.7] depicted in Figure 16. Since there are no other possible edges we can assume that the second vertex of P is the new vertex y 3 and we consider f (y 3 ). Unattached whether the first vertex of P is given by v 2 or v 3 , we have f (y 3 ) = v 7 . If P = (v 2 , y 3 , v 7 ), then we can delete vertex v 3 and its incident edges, which is a contradiction to the minimality of G. If P = (v 3 , y 3 , v 7 ), then the arising graph is isomorphic to the third graph of Figure 14. Thus we may assume that the first vertex of P is given by v 4 and the second vertex is given by y 3 . This P has length at most three and connects the two connected components we have the possibilities (v 4 , y 3 , v 5 ), (v 4 , y 3 , v 6 ), or (v 4 , y 3 , y 4 , v 7 ), see the three graphs on the left hand side of Figure 16. For case [3.3] there is obviously an orientation H satisfying diam 0 (H, D) = 6, diam 1 (H, D) = 8, and diam 2 (H, D) = 10, see Figure 5. In cases [3.1] and [3, 2] we consider the two connected components arising by deleting the edge {v 7 , v 6 }. Let P be a shortest connecting path starting at vertex v 7 . P has length two since otherwise vertex y 3 can be deleted without creating a bridge. So let us denote the second vertex of P by y 4 . If the third vertex on P is an element of {v 2 , v 3 , y 1 , y 2 }, then we can delete vertex y 3 without creating a bridge, which contradicts the minimality of G. If the third vertex of P is given by y 3 then G contains the graph of case [3.3] as a subgraph. Thus the third vertex of P is either given by v 5 or v 6 .

[4.1.1] v f f v f f v f f f f f f f f y 5 d d [4.1.2] v f f v f f v f f f f f f f [4.1.3] v f f v f f v f f f f f f f
If P = (v 7 , y 4 , v 5 ) in case [3.2], then the edge {v 4 , v 5 } is redundant, which contradicts the minimality of G. If P = (v 7 , y 4 , y 6 ) in case [3.1], then we can easily check that adding a connecting path of G -{v 5 , v 6 } produces at least one redundant edge. The two remaining possibilities are given by the graphs of case [3.4] and case [3.5] in the middle of Figure 16. In both cases we can easily give a suitable orientation, see Figure 5.

Next we extend the cases [3.6] and [3.7] on the right hand side of Figure 16. Deleting the edge {v 6 , v 7 } results in two connected components. Let P we a connecting path starting in v 7 . The second vertex of P has to be new vertex, call it y 5 . We can easily check that the resulting graph would not be minimal if we add a path being different from P 1 = (v 7 , y 5 , v 6 ) and P 2 = (v 7 , y 5 , v 5 ). Due to the minimality of G and due to the edge {v 5 , v 6 } we cannot have path P 2 in case [3.7]. If we would have path P 1 in case [3.6] then deleting the edge {v 5 , v 6 } results in two connected components. Here we can check that adding a connecting path ends up in a bridgeless connected graph which is not minimal. The remaining two possibilities are depicted in Figure 17. We remark that the graph on the right hand side of Figure 17 is isomorphic to the graph on the left hand side of Figure 15, i. e. we have rediscovered case Next we consider all possible extensions of the cases [1] and [2] in Figure 12. First we remark that y 1 cannot have an additional neighbor besides the two depicted in Figure 12. The previous edge e = {v 2 , y 1 } or e = {v 3 , y 1 } would be redundant if an edge {y 1 , v i } is added. If y 1 would have a new neighbor y 3 , then we can consider f (y 3 ) and conclude that vertex y 1 or the previous edge e is redundant. Similar we can argue that v 1 does not have any further neighbors. Thus in case [1] vertex v 2 and in case [2] vertex v 3 is a cut vertex. Since we have exhaustively treated the cases [3], [4], [5], and [6], we can conclude that deleting the edge {v 7 , v 6 } from T 3 and adding a shortest path connecting the two arising connected components ends either in case [1] or case [2]. So up to isomorphism we obtain the three cases of Figure 18.

[4.1.1]. v f f v f f v f f f d d d d f v f f v f f v f f d d
Let us proceed in extending case [2.2]. Here the only vertices which can have further neighbors are v 3 , v 4 , and v 5 . If G contains the edge {v 3 , v 5 }, then all vertices are fixed. Otherwise vertex v 3 has a new neighbor y 3 with f (y 3 ) = v 4 . So also vertex v 5 has a new neighbor, which can be either y 3 or another vertex y 4 , with f (y 3 ) = v 4 or f (y 4 ) = v 4 . The three bridgeless connected graphs are depicted in Figure 19. As before we refer to Figure 5 for suitable orientations being compatible with Lemma 2.8.

In case [2.1] only the vertices v 3 , v 4 , v 5 , and v 6 can have additional neighbors. If G contains the edge {v 3 , v 6 }, then all vertices are fixed. If G contains the edge {v 3 , v 5 }, then there has to be a new neighbor

x h h x h h x h h y 1 d d y 2 [1.1] x h h x h h x h h y 1 d d y 2 [2.1] x h h x h h x h h y 1 y 2 d d d d [2.2]
Fig. 18: Fixing v7 for a maximum backbone tree of type 1 in case y 3 of v 6 with f (y 3 ) = v 4 . Both resulting graphs are bridgeless connected and drawn on the left hand side of Figure 20. In the remaining cases we can assume that there are no edges with both end vertices from {v 3 , . . . , v 6 }. Thus v 6 has a new neighbor y 3 with f (y 3 ) = v 4 . The same is true for vertex v 3 . If the new neighbor of v 3 coincides with y 3 , then we obtain a bridgeless connected graph being isomorphic to the graph in the middle of Figure 20. Otherwise v 3 has another new neighbor y 4 with f (y 4 ) = v 4 , see the graph on the right hand side of Figure 20. Suitable orientations can be found in Figure 5.

[1] or case [2]. v f f v f f v f f d d d d v f f v f f v f f f d d d d d d v f f v f f v f f f f d d d d d d
In case [1.1] only the vertices v 2 , . . . , v 5 can have additional neighbors. If G contains the edge {v 2 , v 6 }, then all vertices are fixed. If G contains the edges {v 2 , v 5 } and {v 3 , v 6 }, then all vertices are fixed. Due to symmetry we assume next that G contains the edge {v 2 , v 5 } but does not contain the edge {v 3 , v 6 }. In this case v 6 has a new neighbor y 3 with f (y 3 ) = v 4 . If G contains the edge {v 3 , v 5 }, then vertex v 2 has a new neighbor y 3 with f (y 3 ) = v 4 . The same argument is valid for vertex v 6 . Either those two new vertices coincide or they are different. Since in both cases the edge {v 3 , v 5 } would be redundant we can assume in the following part, concerning case In the remaining cases we assume that the maximum backbone tree T 3 is isomorphic to the tree on the right hand side of Figure 11, i. e. G does not contain the tree on the left hand side of Figure 11 as a subgraph. First we remark that the only possible edge with both endpoints in {v 1 , . . . , v 6 } is given by e := {v 3 , v 4 }. If we delete the edge {v 3 , v 5 } we obtain two connected components and there exists a path P connecting v 5 with a vertex in {v 1 , . . . , v 4 , v 6 }. Let us denote new vertices by y 1 and y 2 . Since G does not contain a backbone tree of type 1 as a subgraph we cannot have P = (v 5 , y 1 , y 2 , v 1 ) or P = (v 5 , y 1 , y 2 , v 6 ). Thus P has length 2. Using the same argument as before we conclude that also P = (v 5 , y 1 , v 4 ) is not possible and the only remaining possibilities are P = (v 5 , y 1 , v 3 ) or P = (v 5 , y 1 , v 2 ). In both cases y 1 cannot have an additional neighbor in {v 1 , . . . , v 6 } due to the minimality of G. Due to symmetry the same argumentation applies for vertex v 6 via deleting the edge {v 4 , v 6 }. Thus, up to symmetry, we obtain the three cases of Figure 22.

In all three cases there exists a path P connecting vertex v 1 with the other component. Since G does not contain a backbone tree of type 1 as a subgraph P has length 2 and cannot end in vertex v 3 or v 4 . Due to the minimality of G the path P cannot end in vertex y 1 or y 2 . Thus we have P = (v 1 , y 3 , v 2 ), where y 3 denotes a new vertex.

For case [C], we obtain a bridgeless connected graph, see the graph on the right hand side of Figure 23. For case [B] we obtain the second graph of Figure 23. By deleting the edge {v 2 , v 3 } we obtain two connected components. We can check that appending a connecting P results in a subgraph being isomorphic to a backbone tree of type 1. Thus it remains to consider case [A]. Here we consider the two connected components arising after the deletion of the edge {v 2 , v 3 }. The only possibility to append a connecting path without creating a subgraph being isomorphic to a backbone tree of type 1 is the path (v 3 , v 4 ), i. e. we add the edge {v 2 , v 4 }, see the graph on the left hand side of Figure 23. Suitable orientations for the two surviving bridgeless connected minimal subgraphs can be found in Figure 5. Finally we have determined the exhaustive list of minimal subgraphs for γ = 3, see Figure 5.

In principle one can implement a computer program which, for a given value of γ, recursively constructs the exhaustive list of possible backbone trees T γ . As a next step one can recursively construct all possibilities for the graphs G k by fixing node by node, i. e. deleting the first bridge of the current graph and appending a connecting path of length at most three in all possible ways. The intermediate graphs can be checked whether they violate the minimality condition (which has to be slightly reformulated in order to be applicable for partial minimal subgraphs). If all graphs are extended until they are bridgeless connected then isomorphic copies and non-minimal graphs have to be removed. The final step is to determine a minimal orientation for each graph. So what we did by hand for γ = 3 can in principle be done by a computer program for all finite values of γ.

GG

  be a strongly connected directed graph. By diam( → G) we denote the diameter of → G. For a simple connected graph G without bridges we define M OD(G) := min diam( is a strongly connected orientation of G , which we call the minimum oriented diameter of a simple graph G. By γ(G) we denote the smallest cardinality of a dominating set of G.

  2

Fig. 1 :Fig. 2 :

 12 Fig. 1: Examples with large minimum oriented diameter in dependence of the domination number γ(G) -the bad examples.

Fig. 3 :

 3 Fig. 3: Graph transformation to fulfill condition (3) of Definition 2.2 Now we look at all edges e of G 3 . If G 3 -e is bridgeless connected with dominating set D we iteratively delete e from G 3 until no such edge exists. The resulting pair (G 4 , D 4 ) fulfills γ(G 4 ) = γ(G 3 ) and M OD(G 4 ) ≥ M OD(G 3 ) as γ(G 4 ) < |D| would be a contradiction to the minimality of D. Thus (G 4 , D) satisfies conditions (1)-(4). Finally we consider all vertices d ∈ D. If |D| = 1 we set k = 2 otherwise we set k = 1. If there are k < k isolated triangles associated with d we add k -k isolated triangles. If there are more than k > k isolated triangles associated with d we delete k -k isolated triangles. For two vertices x and y in two different isolated triangles being associated with the same vertex v we have d(x, y) ≤ 4 in every strongly connected orientation, which yields M OD(G 5 ) ≥ M OD(G 4 ) for the resulting graph G 5 . It is easy to check that (G 5 , D) satisfies conditions (1)-(5).2

Fig. 4 :

 4 Fig. 4: The two possible subgraphs for γ(G) = 2.

  First we observe that the examples from Figure 1 yield Ξ(1) ≥ 4 and Ξ(2) ≥ 8. For the other direction let (G, D) be a pair in standard form attaining M OD(G) = Ξ(γ(G)). For γ(G) = 1 we have |D| = 1, choose the single vertex of D as a subgraph and apply Lemma 2.4.

Fig. 5 :

 5 Fig. 5: The orientations for the proof of Lemma 2.8.

Fig. 6 :

 6 Fig. 6: The situation of Lemma 3.3.

Fig. 7 :

 7 Fig. 7: The situation of Lemma 3.5.

Fig. 8 :

 8 Fig. 8: The situation of Lemma 4.3 and Lemma 4.4.

  set D := D\ v 3 , v 6 , . . . , v 3k-3 is a dominating set of G with | D| = |D| -k + 1. Let H be a minimal orientation of ( G, D). We construct an orientation H of G by keeping the directions of all common edges with H and by orienting the edges of C from v j to v j+1 , see the graph on the left hand side in Figure8.Now we analyze the distances in H. For brevity we set I := v 3j : 0 ≤ j < k (these are the vertices in G which are identified with v 0 in G). The distance of two vertices in I in the orientation H is at most 3k -3 and the distance of two vertices in V (C) is at most 3k -1. Thus we may assume |D| > k. Let a, b be vertices in V (G). If a ∈ I we set ã = v 0 otherwise we set ã = a. Analogously we set b = v 0 for b ∈ I and b = b otherwise. Let P be an arbitrary shortest path in H connecting ã and b. It may happen that this path P does not exist in H since it may contain the vertex v 0 corresponding to two different vertices v 3i and v 3j in G or it may contain one of the edges {v 0 , v j }, {v 0 , u j }, or {u j , v j } with 3 j. Now we want to construct a path P which connects a and b in H. The path P may use one of the edges {v 0 , v j }, {v 0 , u j }, or {u j , v j } with 3 j. Deleting all these edges decomposes P into at least two parts P1 , . . . , Pm with | P1 | + | Pm | ≤ | P | -1. Using a suitable segment C of the cycle C we obtain a path P = P1 ∪ C ∪ Pm of length at most | P1 | + | Pm | + | C| ≤ | P | + 3k -2 in H. If P does not use any of these edges then v 0 is used in P corresponding to two different vertices v 3i and v 3j in G. In this case we can use a suitable segment C of the cycle C, which starts and ends in a vertex of I, to obtain a path P connecting a and b in H of length at most | P | + 3k -3. Thus in general we have d H (a, b) ≤ | P | + 3k -1 and in some special cases we have the following slightly better bounds: (i) If a and b are elements of {v j : 0 ≤ j < 3k} then we have d H (a, b) ≤ 3k -1. (ii) If a, b ∈ I then d H (a, b) ≤ 3k -3. (iii) If |{a, b} ∩ I| = {a, b} ∩ {v j : 0 ≤ j < 3k} = 1 then d H (a, b) ≤ | P | + 3k -2.

  C) ∪ D). Due to Lemma 4.3 we can assume y ≥ 1. Since the two neighbors on the cycle C of a vertex in Y both are not contained in D and exactly one neighbor on the cycle C of a vertex in v ∈ V (C)\(D ∪ Y ) is contained in D we have |C| = 3k + y ≥ 7. On the right hand side of Figure 8 we have depicted an example with k = 2 and y = 4. Now we consider another graph G arising from G by:

  For a 1 , b 1 ∈ A we have d H (a 1 , b 1 ) ≤ 3k + y + 3 ≤ 4(k + y) -2, for a 2 , b 2 ∈ V (C) we have d H (a 2 , b 2 ) ≤ 3k + y -1 ≤ 4(k + y) -4, and for a 3 , b 3 ∈ V (C) ∩ D we have d H (a 3 , b 3 ) ≤ 3k + y -3 ≤ 4(k + y) -2. Thus we may assume |D| > k + y. Let a, b be vertices in V (G). If a ∈ A we set ã = v 0 and ã = a otherwise. Analogously we set b = v 0 for b ∈ A and b = b otherwise. Let P be a shortest path in H connecting ã and b. Similarly as in the proof of Lemma 4.3 we construct a path P in H connecting a and b. If P uses vertex v 0 for a, b / ∈ A we obtain a path P by inserting a segment C of C connecting two dominating vertices. Since | C| ≤ 3k + y -2 we have d H (a, b) ≤ | P | + 3k + y -2 in this case. If |{a, b} ∩ A| = 1 we have d H (a, b) ≤ | P | + 3k + y since for every vertex of A there is a vertex in D ∩ V (C) at distance at most two (in both directions).

v 7 ĜFig. 9 :

 79 Fig. 9: An example for the construction of Ĝ from G.

Fig. 11 :

 11 Fig. 11: The two possible trees T3 for γ = 3.

Fig. 13 :

 13 Fig. 13: Fixing v7 for a maximum backbone tree of type 1 in case [5].

Fig. 15 :

 15 Fig. 15: Fixing v7 for a maximum backbone tree of type 1 in case [4.1].

Fig. 16 :

 16 Fig. 16: Fixing v7 for a maximum backbone tree of type 1 in case [3].

Fig. 17 :

 17 Fig. 17: Extensions for a maximum backbone tree of type 1 in the cases [3.6] and [3.7].

Fig. 19 :

 19 Fig. 19: Fixing v5 for a maximum backbone tree of type 1 in case [2.2].

Fig. 20 :Fig. 21 :

 2021 Fig. 20: Fixing v5 for a maximum backbone tree of type 1 in case [2.1].

Fig. 22 :

 22 Fig. 22: Extensions of a maximum backbone tree of type 2.

Fig. 23 :

 23 Fig. 23: Extensions of the cases [A], [B], and [C] for a maximum backbone tree of type 2.

  we give suitable orientations for all cases. It remains to check that we have diam 0 (H, D) ≤ 7, diam 1 (H, D) ≤ 9, and diam 2 (H, D) ≤ 11 for all given orientations H. 2 Definition 2.9 Let (G , D) be in standard form and G a minimal subgraph. By adding isolated triangles to G we can obtain a graph G such that ( G, D) is in standard form. We say that H is a minimal orientation of G, if H is strongly connected and we have M OD( G) = max diam 0 (H, D) + 4, diam 1 (H, D) + 2, diam 2 (H, D) .

	Using the same notation we have M OD(G ) ≤ M OD( G).
	Definition 2.10 We call a pair (G , D) in standard form critical, if Ξ γ(G ) = M OD(G ) and we call
	a minimal subgraph G of (G , D) in standard form critical if for a minimal orientation H of G we have
	Ξ γ(G ) = max diam 0 (H, D) + 4, diam 1 (H, D) + 2, diam 2 (H, D) .
	Combined with Lemma 2.4 we obtain:
	Lemma 2.11 For each integer γ there is a pair (G , D) in standard form with |D| = γ and a critical
	minimal subgraph G such that Ξ(γ) equals max {diam 0 (H, D) + 4, diam 1 (H, D) + 2, diam 2 (H, D)}
	for a minimal orientation H of G.

  Definition 4.1 We call (G, G , D) a counter example to Theorem 1.3 if (G , D) is in standard form, G a minimal subgraph, and max diam 0 (H, D) + 4, diam 1 (H, D) + 2, diam 2 (H, D) > 4|D| for every orientation H of G. If |D| is minimal with respect to this property we call it a minimal counter example.

	Lemma 4.2 For a minimal counter example (to Theorem 1

Acknowledgements

We are very grateful to the anonymous referees for pointing out a gap in a previous version of this paper and their many suggestions to improve the presentation of our result.

2

In the following we want to show that for a minimal counter example (G, G , D), where we cannot apply the reductions from one of the previous lemmas, the number of vertices in G will be that small that every strongly connected orientation of G can be used in combination with Lemma 2.4 to deduce M OD(G ) ≤ 4 • |D| = 4 • γ(G ). For this purpose we slightly enhance the concept of the trees T k of Construction 2.5 a bit: Definition 4.5 Let G be a minimal subgraph of (G , D) in standard form. We call a subgraph T of G a backbone tree of We remark that the existence of a backbone tree is guaranteed by Construction 2.5 and the order of a backbone tree is bounded from above: Lemma 4.6 For each backbone tree T of a minimal subgraph G of (G , D) in standard form we have

Proof: Iteratively we construct trees T k for k = 1, . . . , |D| which are subgraphs of T and satisfy

The tree T 1 is composed of one vertex x 1 in D. To construct T k+1 from T k we find a vertex x k+1 in D\V (T k ) with minimum distance to T k in T . Let P = (v 1 , . . . , v l , x k+1 ) be the corresponding shortest path. Next we show |V (P )\V (T k )| ≤ 3 so that appending P to T k yields a tree T k+1 with |T k+1 ∩D| = k+1 and |V (T k+1 )| ≤ 3(k+1)-2. For this purpose we observe that v 2 , . .

))) would be a shorter path than P . Thus finally we end up with a tree

It remains to show that T |D| = T . Suppose that there is a vertex v ∈ V (T )\V (T |D| ). Since v / ∈ D is not a leaf there exists a neighbor u ∈ V (T )\D, i. e. u = f (v), and we conclude that the edges of R = (f (v), v, u, f (u)) are contained in E(T ). Since there is a path S connecting f (v) and f (u) in T |D| the path R and S form a cycle in T , which is a contradiction.

2

An example of a backbone tree is given in Figure 10, where the graph on the left hand side is a backbone tree of the graph on the left hand side of Figure 9.

Lemma 4.7 Let (G, G , D) be a minimal counter example to Theorem 1.3 and T be a maximum backbone tree of G. Then for every edge {u, v} ∈ E(G) we have {u, v} ∩ V (T ) = ∅.

Proof: Suppose to the contrary that there is an edge {u,

For |D| > 1 this special cut vertex has to be contained in T so that we have {u, v} ∩ V (T ) = ∅ in this case.

Adding the path P = (f (u), u, v, f (v)) to T yields a cycle C = (v 0 , . . . , v l-1 ) containing f (u), u, v, and f (v). Due to Lemma 4.3 there exists an index i such that v i-1 , v i , v i+1 / ∈ D, where the indices are read modulo l, i. e. v -1 = v l-1 and v l = v 0 . W.l.o.g. we assume v i+2 ∈ D and construct another backbone tree T as follows. If v i+1 has another neighbor besides v i and f

would also be bridgeless connected, which is a contradiction to the minimality of G. Thus we have v 2 = u 2 in this case.

(c) f (v 2 ) = z: This case is not possible as G-v 3 would also be bridgeless connected otherwise, which is a contradiction to the minimality of G.

By symmetry we can conclude

As in the proof of Lemma A.1 we define G as the graph arising from G by deleting the vertices u i , v i and by identifying x, y and z. Obviously G is connected and bridgeless. Now let D := D\{y, z} and H be an arbitrary minimal orientation of G. Thus we have

We construct an orientation H of G by directing the two pairs of walks (W 1 , W 3 ), (W 2 , W 4 ) in opposite directions such that the two paths (v 3 , y), (y, v 4 ) are directed differently, by taking the directions from H and by directing remaining edges arbitrarily.

Now we analyze the distance

We can easily check that d H (u, v) ≤ 9 for u, v ∈ I ∪ {x, y, z}. Thus we have

We remark that Lemma A.2 applies to a graph containing two copies of the graph on the right hand side of Figure 4 as an induced subgraph for x, y, z ∈ D depicted by solid circles, where the vertices depicted by empty circles have no further neighbors in the whole graph.

If the number of arising components in the setting of Lemma 3.1 or Lemma 3.2 is at least three, then we can obtain a reduction being compatible with our conjecture on Ξ(γ).

Proof: We can rephrase most of the proof of Lemma 3.1. Our estimations on diam i (H, D) remain valid. Since there are at least three connected components we have γ i + γ j ≤ γ -2 for all i = j. Using this and Ξ(n -1) ≤ Ξ(n) we conclude Ξ(γ) ≤ max Ξ(γ -i) + Ξ(i) -4 : 1 ≤ i ≤ γ -1 . 2

Lemma A.4 Let G be a critical minimal subgraph of (G , D) in standard form with γ = γ(G ) = |D| ≥ 3, x a vertex not contained in the dominating set D, and C 1 , . . . , C r the connected components of G -x.

If r ≥ 3, then we have Ξ(γ) ≤ max Ξ(i) + Ξ(γ + 1 -i) -7, Ξ(i -1) + Ξ(γ + 1 -i) -4 : 2 ≤ i ≤ γ -1 .