On optimal orientations of cartesian products of trees

Abstract

Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G × H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D) = r(G) and d(D) = d(G). Let {T2}, i = 1 , . . . , n, where n ≥ 2, be a family of trees. In this paper, we show that the graph Πi=1 n Ti admits an (r, d)-invariant orientation provided that d(Ti) ≥ d(T2) ≥ 4 for n = 2, and d(Ti) ≥ 5 and d(T2) ≥ 4 for n ≥ 3. © Springer-Verlag 2001.