On optimal orientations of Cartesian products of even cycles

K.M. Koh, Eng Guan Tay · Networks · 1998

For a graph G, let 𝒟 (G) be the family of strong orientations of G. Define d̄ (G) = min {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

Read the paper · More papers on PaperTik