On optimal orientations of cartesian products with a bipartite graph

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) (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. In this paper, we show that ρ(G×A1×A2××Ak)=0, where G is a bipartite graph fulfilling certain weak conditions and {Ai|1≤i≤k} is certain combination of graphs. © 1999 Elsevier Science B.V.