On optimal orientations of cartesian products of graphs (I)

Abstract

For a graph G, let script D sign(G) be the family of strong orientations of G, and define d⇀(G)= min{d(D)] D ∈ script D sign(G)}, where d(D) denotes the diameter of the digraph D. Let G x H denote the cartesian product of the graphs G and H. In this paper, we determine completely the values of d⇀(Km x Pn), d⇀(Km x Kn) and d⇀(Kn x C2k+1), except d⇀(K3 x C2k+1), k≥2, where Kn, Pn and Cn denote the complete graph, path and cycle of order n, respectively. © 1998 Elsevier Science B.V. All rights reserved.