ISSN 2590-9770
The Art of Discrete and Applied Mathematics 2 (2019) #P1.04
https://doi.org/10.26493/2590-9770.1246.99c
(Also available at http://adam-journal.eu)
Optimal orientations of strong products of paths
Tjaša Paj Erker
University of Maribor, FME, Smetanova 17, 2000 Maribor, Slovenia
Received 9 March 2018, accepted 13 July 2018, published online 8 August 2018
Abstract
Let diammin(G) denote the minimum diameter of a strong orientation of G and let
G  H denote the strong product of graphs G and H . In this paper we prove that
diammin(Pm  Pn) = diam(Pm  Pn) for m,n ≥ 5, m 6= n, and diammin(Pm  Pn) =
diam(Pm  Pn) + 1 for m,n ≥ 5, m = n. We also prove that diammin(G  H) ≤
max {diammin(G),diammin(H)} for any connected bridgeless graphs G and H .
Keywords: Diameter, strong orientation, strong product.
Math. Subj. Class.: 05C12, 05C76
1 Introduction
Let D = (V (D), A(D)) be a directed graph. If (u, v) ∈ A(D), we write u → v. A
uv-path is a directed path u = u1u2 . . . un = v from a vertex u to a vertex v. The length of
the path u = u1u2 . . . un = v is n− 1. If every vertex in D is reachable from every other
vertex in D, we say that directed graph D is strong (there is a directed uv-path in D for
every u, v ∈ V (D)). The distance from u to v is the length of a shortest directed uv-path
in D, denoted by distD(u, v). The greatest distance among all pairs of vertices in D is the
diameter of D, so
diam(D) = max{distD(u, v) | u, v ∈ V (D)}.
Note that the distance of two vertices u, v in undirected graph G, distG(u, v), is the length
of a shortest undirected uv-path in G and the greatest distance between any two vertices in
G is the diameter of G, denoted by diam(G).
Let G be an undirected graph. An orientation of G is a digraph D obtained from G
by assigning to each edge in G a direction. Let D(G) denote the family of all strong
orientations of G. In [9] it is proved that every connected bridgeless graph admits a strong
orientation. We define the minimum diameter of a strong orientation of G as
diammin(G) = min{diam(D) | D ∈ D(G)}.
E-mail address: tjasa.paj@um.si (Tjaša Paj Erker)
cb This work is licensed under http://creativecommons.org/licenses/by/3.0/
2 Art Discrete Appl. Math. 2 (2019) #P1.04
The parameter diammin(G) was studied by many authors, because it is important from
theoretical and practical points of view, as an application in traffic control problems. Ori-
entations of graphs can be viewed as arrangements of one-way streets, if G is thought of
as the system of two-way streets in a city, and we want to make every street in the city
one-way and still get from every point to every other point (see [9, 10]).
For every bridgeless connected graph G of radius r it was shown, see [1], that
diammin(G) ≤ 2r2+2r. There were also some determined values of the minimum diame-
ter of a strong orientation of the Cartesian product of graphs. For Cartesian product of two
paths it was proved that diammin(Pm Pn) = diam(Pm Pn), for m ≥ 3 and n ≥ 6,
see [5]. In [8] it was proved that diammin(Cm Cn) = diam(Cm Cn) for m,n ≥ 6. In
[7] Koh and Tay proved that diammin(T1 T2) = diam(T1 T2) for trees T1 and T2 with
diameters at least 4. They also studied the diameter of orientations of Km Kn, Km Pn,
Pm Cn and Km Cn (see [4, 5, 6]).
In [3], the upper bound for the strong radius and the strong diameter of Cartesian prod-
uct of graphs are determined.
In this article we consider the minimum diameter of strong orientations of strong prod-
ucts of graphs. The strong product of graphs G and H is the graph, denoted by GH , with
the vertex set V (G H) = V (G) × V (H) where two distinct vertices (u, v) and (u′, v′)
are adjacent in GH if and only if uu′ ∈ E(G) and v = v′, or u = u′ and vv′ ∈ E(H),
or uu′ ∈ E(G) and vv′ ∈ E(H). For v ∈ V (H) we define the G-layer Gv:
Gv = {(u, v) | u ∈ V (G)} .
Analogously we define H-layers.
In the next section we prove that diammin(PmPn) = diam(PmPn), for m,n ≥ 5,
m 6= n and that diammin(Pm  Pn) = diam(Pm  Pn) + 1, for m,n ≥ 5, m = n.
2 Orientations of Pm  Pn
In [7] Koh and Tay proved that diammin(Pm Pn) = diam(Pm Pn), for m ≥ 5 and
n ≥ 5. We use some of their notations. So we will define four sections of V (Pm  Pn)
and two basic orientations of Ps Pt, where s, t ≥ 3, similarly as it was introduced in [7].
For m,n ≥ 5 we define
(i) Southwest Section SW =
{
(i, j) | 1 ≤ i ≤
⌈
m
2
⌉
, 1 ≤ j ≤
⌈
n
2
⌉}
;
(ii) Northwest Section NW =
{
(i, j) | 1 ≤ i ≤
⌈
m
2
⌉
,
⌈
n+1
2
⌉
≤ j ≤ n
}
;
(iii) Southeast Section SE =
{
(i, j) |
⌈
m+1
2
⌉
≤ i ≤ m, 1 ≤ j ≤
⌈
n
2
⌉}
;
(iv) Northeast Section NE =
{
(i, j) |
⌈
m+1
2
⌉
≤ i ≤ m,
⌈
n+1
2
⌉
≤ j ≤ n
}
.
We define two basic orientations of Ps  Pt, where s, t ≥ 3: if s ≤ t, we define the
orientation F1 of Ps  Pt as:
(i) For 1 ≤ i ≤ s− 1 and 2 ≤ j ≤ t, (i, j)→ (i+ 1, j − 1);
(ii) For 1 ≤ i ≤ s − 1 and 1 ≤ j ≤ t − 1, (i + 1, j + 1) → (i, j) if j − i ≥ t − s and
(i, j)→ (i+ 1, j + 1) if j − i < t− s;
(iii) For 1 ≤ i ≤ s− 1 and 2 ≤ j ≤ t, (i, j)→ (i, j − 1);
(iv) For 1 ≤ j ≤ t− 1, (s, j)→ (s, j + 1);
T. Paj Erker: Optimal orientations of strong products of paths 3
(v) For 1 ≤ i ≤ s− 1 and 1 ≤ j ≤ t− 1, (i, j)→ (i+ 1, j);
(vi) For 2 ≤ i ≤ s, (i, t)→ (i− 1, t);
and if s > t, we define the orientation F2 of Ps  Pt as:
(i) For 2 ≤ i ≤ s and 1 ≤ j ≤ t− 1, (i, j)→ (i− 1, j + 1);
(ii) For 1 ≤ i ≤ s and 1 ≤ j ≤ t, (i + 1, j + 1) → (i, j) if i − j ≥ s − t and
(i, j)→ (i+ 1, j + 1) if i− j < s− t;
(iii) For 1 ≤ i ≤ s− 1 and 1 ≤ j ≤ t− 1, (i, j)→ (i, j + 1);
(iv) For 2 ≤ j ≤ t, (s, j)→ (s, j − 1);
(v) For 2 ≤ i ≤ s and 1 ≤ j ≤ t− 1, (i, j)→ (i− 1, j);
(vi) For 1 ≤ i ≤ s− 1, (i, t)→ (i+ 1, t).
The orientation F1 of P3  P4 and the orientation F2 of P4  P3 is shown in Figure 1.
F1
(s, t)
F2
(s, t)
Figure 1: Orientations F1 and F2.
Observation 2.1. If s < t, for any (i, j) ∈ V (F1), distF1((i, j), (s, t− 1)) ≤ t− 2.
Proof. Let (i, j) ∈ V (F1). We shall consider four cases.
(i) If j 6= t and j ≥ i+t−s−1, then (i, j)→ (i+1, j)→ · · · → (j−(t−s)+1, j)→
(j− (t− s)+ 2, j+1)→ · · · → (s, t− 1) is a path of length at most s− 1 ≤ t− 2.
(ii) If j 6= t and j < i+ t− s− 1, then (i, j)→ (i+1, j+1)→ · · · → (s, j+ s− i)→
(s, j + s− i+ 1)→ · · · → (s, t− 1) is a path of length at most t− 2.
(iii) If j = t and i 6= s, then (i, t)→ (i+ 1, t− 1)→ (i+ 2, t− 1)→ · · · → (s, t− 1)
is a path of length at most s− 1 ≤ t− 2.
(iv) If j = t and i = s, then (s, t) → (s − 1, t − 1) → (s, t − 1) is a path of length
two.
Observation 2.2. If s < t, for any (i, j) ∈ V (F1), distF1((i, j), (s, t)) ≤ t− 1.
Proof. Since (s, t− 1)→ (s, t), the claim follows by Observation 2.1:
distF1((i, j), (s, t)) = distF1((i, j), (s, t− 1)) + 1 ≤ s− 1 + 1 ≤ t− 1.
Observation 2.3. If s < t, for any (i, j) ∈ V (F1), distF1((s− 1, t), (i, j)) ≤ t− 1.
4 Art Discrete Appl. Math. 2 (2019) #P1.04
Proof. Let (i, j) ∈ V (F1). We shall consider four cases.
(i) If i 6= s and j > i+ t− s, then (s− 1, t)→ (s− 2, t)→ · · · → (i+ (t− j), t)→
(i+ (t− j)− 1, t− 1)→ · · · → (i, j) is a path of length at most s− 2 ≤ t− 2.
(ii) If i 6= s and j ≤ i+ t− s, then (s−1, t)→ (s−1, t−1)→ (s−2, t−2)→ · · · →
(i, i+ t− s)→ (i, i+ t− s− 1)→ · · · → (i, j) is a path of length at most t− 1.
(iii) If i = s and j 6= t, (s − 1, t) → (s − 1, t − 1) → (s − 1, t − 2) → · · · →
(s− 1, j + 1)→ (s, j) is a path of length at most t− 1.
(iv) If i = s and j = t, then (s− 1, t)→ (s, t− 1)→ (s, t) is a path of length two.
Observation 2.4. If s < t, for any (i, j) ∈ V (F1), distF1((s, t), (i, j)) ≤ t− 1.
Proof. Since (s, t)→ (s−1, t) and (s, t)→ (s−1, t−1), the proof is similar as the proof
of Observation 2.3.
Observation 2.5. If s = t, for any (i, j) ∈ V (F1), distF1((i, j), (s, s)) ≤ s.
Proof. Let (i, j) ∈ V (F1). We shall consider three cases.
(i) If j 6= t and j ≥ i−1, then (i, j)→ (i+1, j)→ · · · → (j+1, j)→ (j+2, j+1)→
· · · → (s, s− 1)→ (s, s) is a path of length at most s.
(ii) If j 6= t and j < i − 1, then (i, j) → (i + 1, j + 1) → · · · → (s, j + s − i) →
(s, j + s− i+ 1)→ · · · → (s, s) is a path of length at most s− 1.
(iii) If j = s and i 6= s, then (i, s)→ (i+1, s−1)→ (i+2, s−1)→ · · · → (s, s−1)→
(s, s) is a path of length at most s.
Observation 2.6. If s = t, for any (i, j) ∈ V (F1), distF1((s, s), (i, j)) ≤ s− 1.
Proof. Let (i, j) ∈ V (F1). We shall consider three cases.
(i) If i 6= s and j > i, then (s, s) → (s − 1, s) → · · · → (i + (s − j), s) →
(i+ (s− j)− 1, t− 1)→ . . .→ (i, j) is a path of length at most s− 1.
(ii) If i 6= s and j ≤ i, then (s, s) → (s − 1, s − 1) → · · · → (i, i) → (i, i − 1) →
. . .→ (i, j) is a path of length at most s− 1.
(iii) If i = s and j 6= s − 1, (s, s) → (s − 1, s − 1) → (s − 1, s − 2) → · · · →
(s− 1, j + 1)→ (s, j) is a path of length at most s− 1.
(iv) If i = s and j = s− 1, then (s, s)→ (s− 1, s− 1)→ (s, s− 1) is a path of length
two.
Similarly as above, we can prove next Observations 2.7–2.10.
Observation 2.7. If s > t, for any (i, j) ∈ V (F2), distF2((s, t− 1), (i, j)) ≤ s− 1.
Observation 2.8. If s > t, for any (i, j) ∈ V (F2), distF2((s, t), (i, j)) ≤ s− 1.
Observation 2.9. If s > t, for any (i, j) ∈ V (F2), distF2((i, j), (s− 1, t)) ≤ s− 2.
Observation 2.10. If s > t, for any (i, j) ∈ V (F2), distF2((i, j), (s, t)) ≤ s− 1.
T. Paj Erker: Optimal orientations of strong products of paths 5
In [7], Koh and Tay also introduced a key-vertex v ∈ V (F ) of digraph F . Let F ∈
D(Ps  Pt). We say that a vertex v ∈ V (F ) is a key-vertex of F if
distF (u, v) ≤ max {t, s} and distF (v, u) ≤ max {t, s}
for all u ∈ V (F ). Note that (s, t) is a key-vertex of F1 and of F2.
Analogously as F1 and F2, we define 6 other isomorphic orientations Fi, 3 ≤ i ≤ 8 of
Ps  Pt as shown in Figures 2 and 3.
F1
F4
F5
F8
Figure 2: Orientations F1, F4, F5 and F8.
Obviously vertices denoted by black dots in Figures 2 and 3 are key-vertices of Fi for
i = 1, . . . , 8 (similar arguments as in Observations 2.1–2.6).
Lemma 2.11. Let m,n ≥ 5, m 6= n and m,n ≡ 1 (mod 2). Then
diammin(Pm  Pn) ≤ max {m− 1, n− 1} .
Proof. Let m < n. We define the orientation D of Pm  Pn by F1, F4, F5 and F8:
(a) orient the section NW as F4;
(b) orient the section NE as F8;
(c) orient the section SW as F1;
(d) orient the section SE as F5.
As an illustration, the orientation of P5  P7 is shown in Figure 4. The vertex z =
(m+12 ,
n+1
2 ) is the key-vertex of each Fi, for i = 1, 4, 5, 8. For any u, v ∈ V (D),
distD(u, v) ≤ distD(u, z) + distD(z, v).
6 Art Discrete Appl. Math. 2 (2019) #P1.04
F2
F3 F7
F6
Figure 3: Orientations F2, F3, F6 and F7.
Since distD(u, z) ≤ n−12 and distD(z, v) ≤
n−1
2 (similarly as in Observation 2.2 and
Observation 2.4), we have
distD(u, v) ≤
n− 1
2
+
n− 1
2
= n− 1.
If m > n we define the orientation D of Pm  Pn by F2, F3, F6 and F7. Similarly as
above, we have
distD(u, v) ≤ distD(u, z) + distD(z, v) ≤
m− 1
2
+
m− 1
2
= m− 1
(see Observation 2.10 and Observation 2.8).
Lemma 2.12. Let m,n ≥ 6, m 6= n and m,n ≡ 0 (mod 2). Then
diammin(Pm  Pn) ≤ max {m− 1, n− 1} .
Proof. Let m < n. Denote z1 = (m2 ,
n
2 ), z4 = (
m
2 ,
n
2 + 1), z5 = (
m
2 + 1,
n
2 ) and
z8 = (
m
2 + 1,
n
2 + 1). We define the orientation D of Pm  Pn by F1, F4, F5 and F8 as
follows:
(a) orient the section NW as F4;
(b) orient the section NE as F8;
(c) orient the section SW as F1;
(d) orient the section SE as F5;
(e) Orient z1 → (m2 −1,
n
2+1), (
m
2 +1,
n
2−1)→ z1, z4 → (
m
2 −1,
n
2 ), (
m
2 +1,
n
2+2)→
z4, z5 → (m2 + 2,
n
2 + 1), (
m
2 ,
n
2 − 1) → z5, z8 → (
m
2 + 2,
n
2 ), (
m
2 ,
n
2 + 2) → z8,
and orient all other edges arbitrarily.
T. Paj Erker: Optimal orientations of strong products of paths 7
1 m+12 m
1
n+1
2
n
F1
F4
F5
F8
Figure 4: The orientation D of P5  P7.
F1
z1
F4
z4
F5
z5
F8
z8
1
m
2
m
2 + 1 m
1
n
2
n
2 + 1
n
Figure 5: The orientation D of P6  P8.
8 Art Discrete Appl. Math. 2 (2019) #P1.04
The orientation D is shown in Figure 5. Note that vertices z1, z4, z5 and z8 are key-vertices
of Fi, for i = 1, 4, 5, 8.
Let u, v ∈ V (D). We claim that distD(u, v) ≤ n− 1. There are four cases.
(i) If u and v are in the same section, then we have
distD(u, v) ≤ distD(u, zi) + distD(zi, v) ≤
n
2
− 1 + n
2
− 1 = n− 2
as in Observation 2.2 and Observation 2.4.
(ii) If u ∈ NW and v ∈ SW, then (see Observation 2.2 and Observation 2.3):
distD(u, v) ≤ distD(u, z4) + distD
(
z4, (
m
2 − 1,
n
2 )
)
+ distD
(
(m2 − 1,
n
2 ), v
)
≤ n
2
− 1 + 1 + n
2
− 1 = n− 1.
The argument is similar if u ∈ SW and v ∈ NW, or u ∈ NE and v ∈ SE, or u ∈ SE
and v ∈ NE.
(iii) If u ∈ SW and v ∈ SE, then the claim follows from Observation 2.1 and Observation
2.4, similarly as above. Also, if u ∈ SE and v ∈ SW, or u ∈ NW and v ∈ NE, or
u ∈ NE and v ∈ NW, then the argument is analogous.
(iv) If u ∈ SW and v ∈ NE, then (see Observation 2.1 and Observation 2.3) we have
distD(u, v) ≤ distD
(
u, (m2 ,
n
2 − 1)
)
+ distD
(
(m2 ,
n
2 − 1), z5
)
+
+ distD
(
z5, (
m
2 + 2,
n
2 + 1)
)
+ distD
(
(m2 + 2,
n
2 + 1), v
)
≤ n
2
− 2 + 1 + 1 + n
2
− 1 = n− 1.
The argument is similar for u ∈ NE and v ∈ SW, or u ∈ NW and v ∈ SE, or
u ∈ SE and v ∈ NW.
Analogously if m > n, we have distD(u, v) ≤ m− 1 for any u, v ∈ V (D).
Lemma 2.13. Let m ≥ 5, n ≥ 6, m ≡ 1 (mod 2) and n ≡ 0 (mod 2). Then
diammin(Pm  Pn) ≤ max {m− 1, n− 1} . (2.1)
Proof. Let m < n. Denote z1 = (m+12 ,
n
2 ) and z4 = (
m+1
2 ,
n
2 + 1). We define the
orientation D of Pm  Pn by F1, F4, F5 and F8 as follows:
(a) orient the section NW as F4;
(b) orient the section NE as F8;
(c) orient the section SW as F1;
(d) orient the section SE as F5;
(e) orient z4 → (m+12 − 1,
n
2 ), z1 → z4, z4 → (
m+1
2 + 1,
n
2 ), and orient all other edges
arbitrarily.
The orientation D is shown in Figure 6. Note that vertex z1 is a key-vertex of F1 and F5
and that vertex z4 is a key-vertex of F4 and F8.
T. Paj Erker: Optimal orientations of strong products of paths 9
F1
z1
F4
z4
F8
1
m
2 m
1
n
2
n
2 + 1
n
Figure 6: The orientation D of P5  P8.
Let u, v ∈ V (D). There are three cases.
(i) If u ∈ NW ∪NE and v ∈ NW ∪NE, then we have
distD(u, v) ≤ distD(u, z4) + distD(z4, v) ≤
n
2
− 1 + n
2
− 1 = n− 2
(see Observation 2.2 and Observation 2.4). The case that {u, v} ⊆ SW ∪ SE is
similar.
(ii) If u ∈ SW∪SE and v ∈ NW∪NE, then (see Observation 2.2 and Observation 2.4):
distD(u, v) ≤ distD(u, z1) + distD(z1, z4) + distD(z4, v)
≤ n
2
− 1 + 1 + n
2
− 1 = n− 1.
(iii) If u ∈ NW ∪NE and v ∈ SW, then from Observation 2.2 and Observation 2.3:
distD(u, v) ≤ distD(u, z4) + distD
(
z4,
(
m+1
2 − 1,
n
2
))
+
+ distD
((
m+1
2 − 1,
n
2
)
, v
)
≤ n
2
− 1 + 1 + n
2
− 1 = n− 1.
The case that u ∈ NW ∪NE and v ∈ SE is similar.
Let m > n. Denote z2 = (m+12 ,
n
2 ) and z3 = (
m+1
2 ,
n
2 + 1). We define the orientation
D of Pm  Pn by F2, F3, F6 and F7 as follows:
(a) orient the section NW as F3;
10 Art Discrete Appl. Math. 2 (2019) #P1.04
(b) orient the section NE as F7;
(c) orient the section SW as F2;
(d) orient the section SE as F6;
(e) orient (m+12 −1,
n
2 )→ z3, z3 → z2, (
m+1
2 +1,
n
2 )→ z3 and all other edges oriented
arbitrarily.
The rest of the proof is analogously as above.
Note that if m ≥ 5 and n ≥ 6, m ≡ 0 (mod 2) and n ≡ 1 (mod 2), we also
have (2.1).
Lemma 2.14. Let m ≥ 5, m ≡ 1 (mod 2). Then
diammin(Pm  Pm) ≤ m.
Proof. Denote z = (m+12 ,
m+1
2 ). We define the orientation D of Pm  Pm by F1, F4, F5
and F8 as follows:
(a) orient the section NW as F4;
(b) orient the section NE as F8;
(c) orient the section SW as F1;
(d) orient the section SE as F5.
Note that z is a key-vertex of Fi, for i = 1, 4, 5, 8. For any u, v ∈ D we have
distD(u, v) ≤ distD(u, z) + distD(z, v) ≤
m+ 1
2
+
m− 1
2
= m
as in Observation 2.5 and Observation 2.6.
Lemma 2.15. Let m ≥ 6, m ≡ 0 (mod 2). Then
diammin(Pm  Pm) ≤ m.
Proof. The proof is similarly as the proof of Lemma 2.12 (it follows from Observations 2.1,
2.3, 2.5 and 2.6).
In [2], it is proved that if (u, v) and (u′, v′) are vertices of a strong product GH , then
distGH((u, v), (u
′, v′)) = max{distG(u, u′),distH(v, v′)}.
Since diam(Pm) = m − 1, we get diam(Pm  Pn) = max{m − 1, n − 1}. Since
diam(Pm  Pn) = distPmPm((1, 1), (m,m)) = m − 1 and there is only one path from
(1, 1) to (m,m) in Pm  Pm possessing the length m− 1, it follows that
distD((1, 1), (m,m)) > m− 1 or distD ((m,m), (1, 1)) > m− 1
for any D ∈ D(Pm  Pn). To combine these two observations with Lemmas 2.11–2.15,
we obtain the following theorem:
T. Paj Erker: Optimal orientations of strong products of paths 11
Theorem 2.16. If m,n ≥ 5, then
diammin(Pm  Pn) =
{
diam(Pm  Pn), if m 6= n;
diam(Pm  Pn) + 1, if m = n.
At the end of this section, we give the bounds of diammin(Pn  Pm) for m < 5.
From Figure 7, we see that n − 1 ≤ diammin(Pn  P2) = n for n > 2, n − 1 ≤
diammin(Pn  P3) = n for n > 3 and n− 1 ≤ diammin(Pn  P4) = n+ 1 for n > 4.
· · ·
· · ·
· · ·
Pn
Pn
Pn
P2
P3
P4
Figure 7: Orientations of Pn  P2, Pn  P3 and Pn  P4.
3 Strong orientation of graphs
In this section we shall prove the next theorem.
Theorem 3.1. Let G and H be connected bridgeless graphs. Then
diammin(GH) ≤ max{diammin(G),diammin(H)}.
Proof. Let DG be a strong orientation of G such that diam(DG) = diammin(G) = d1 and
let DH be a strong orientation of H such that diam(DH) = diammin(H) = d2. We define
the orientation DGH of GH as:
(a) Every edge with endvertices in layers Gv , v ∈ V (H) gets the orientation DG.
(b) Every edge with endvertices in layers Hu, u ∈ V (G) gets the orientation DH .
(c) If u→ u′ in G and v → v′ in H , then (u, v)→ (u′, v′), all other edges are oriented
arbitrarily.
12 Art Discrete Appl. Math. 2 (2019) #P1.04
We have to prove that for every pair of vertices (u, v), (u′, v′) in G  H there is a
directed path P from (u, v) to (u′, v′) in DGH , such that the length of P is at most
max {d1, d2}.
If (u, v) and (u′, v) are vertices in the same G-layer or if (u, v) and (u, v′) are vertices
in the same H-layer, then there is a directed path from (u, v) to (u′, v) in DGH of length
at most d1 or a directed path from (u, v) to (u, v′) of length at most d2.
Now let (u, v) and (u′, v′) be arbitrary vertices in DGH . There is a directed path u =
u1u2 . . . um = u
′ in G of length at most d1 and there is a directed path v = v1v2 . . . vn = v′
in H of length at most d2. Without loss of generality we can assume m ≥ n. We have
(u, v)→ (u2, v2)→ (u3, v3)→ · · · → (un, vn)→
(un+1, vn)→ · · · → (um, vn) = (u′, v′)
is a path of length at most d1.
Since diammin(C3) = 2 and diammin(C3  C3) = 2, the bound is tight.
References
[1] V. Chvátal and C. Thomassen, Distances in orientations of graphs, J. Comb. Theory Ser. B 24
(1978), 61–75, doi:10.1016/0095-8956(78)90078-3.
[2] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Discrete Mathematics
and its Applications, CRC Press, Boca Raton, Florida, 2nd edition, 2011, doi:10.1201/b10959.
[3] J. S.-T. Juan, C.-M. Huang and I. Sun, The strong distance problem on the Cartesian product
of graphs, Inform. Process. Lett. 107 (2008), 45–51, doi:10.1016/j.ipl.2008.01.001.
[4] K. M. Koh and E. G. Tay, On optimal orientations of Cartesian products of even cycles and
paths, Networks 30 (1997), 1–7, doi:10.1002/(sici)1097-0037(199708)30:1〈1::aid-net1〉3.0.co;
2-h.
[5] K. M. Koh and E. G. Tay, Optimal orientations of products of paths and cycles, Discrete Appl.
Math. 78 (1997), 163–174, doi:10.1016/s0166-218x(97)00017-6.
[6] K. M. Koh and E. G. Tay, On optimal orientations of Cartesian products of graphs (II): com-
plete graphs and even cycles, Discrete Math. 211 (2000), 75–102, doi:10.1016/s0012-365x(99)
00136-3.
[7] K. M. Koh and E. G. Tay, On optimal orientations of Cartesian products of trees, Graphs
Combin. 17 (2001), 79–97, doi:10.1007/s003730170057.
[8] J.-C. Konig, D. W. Krumme and E. Lazard, Diameter-preserving orientations of the torus, Net-
works 32 (1998), 1–11, doi:10.1002/(sici)1097-0037(199808)32:1〈1::aid-net1〉3.3.co;2-a.
[9] H. E. Robbins, Questions, discussions, and notes: A theorem on graphs, with an application to
a problem of traffic control, Amer. Math. Monthly 46 (1939), 281–283, doi:10.2307/2303897.
[10] F. S. Roberts and Y. Xu, On the optimal strongly connected orientations of city street graphs I:
Large grids, SIAM J. Discrete Math. 1 (1988), 199–222, doi:10.1137/0401022.