On optimal orientations of Cartesian products of even cycles

Abstract

For a graph G, let D(G) be the family of strong orientations of G. Define d⇀(G) = min {d(D) \ D ∈ D(G)} and ρ(G) = d⇀(G) - d(G), where d(D) [respectively, d(G)] denotes the diameter of the digraph D (respectively, graph G). Let G × H denote the Cartesian product of the graphs G and H, and Cp, the cycle of order p. In this paper, we show that ρ(C2m × C2n) = 0 and ρ(C2m × C2n × G1 × G2 × ⋯ × Gk) = 0, where {Gi | 1 ≤ i ≤ k} is any combination of paths and cycles. © 1998 John Wiley & Sons, Inc. Networks 32: 299-306, 1998.