On optimal orientations of cartesian products of graphs (II): Complete graphs and even cycles

Abstract

For a graph G, let script D sign(G) be the family of strong orientations of G. Define d⇀(G)=min{d(D) /D ∈ script D sign(G)} and ρ(G) = d⇀(G) - d(G), where d(D) (resp., d(G)) denotes the diameter of the digraph D (resp., graph G). Let G × H denote the cartesian product of the graphs G and H, Kp the complete graph of order p and Cp the cycle of order p. In this paper, we show that ρ(K2 × C2m) = 2, ρ(Kn × C2m) = 1 for n = 3,4,5,7, and ρ(Kn × C2m) = 0 for most cases otherwise. © 2000 Elsevier Science B.V. All rights reserved.