The diameter of strong orientations of strong products of graphs

Abstract

Let G and H be graphs, and G☒H the strong product of G and H. We prove that for any connected graphs G and H there is a strongly connected orientation D of G☒H such that diam(D) ≤ 2r+15, where r is the radius of G☒H. This improves the general bound diam(D) ≤ 2r²+2r for arbitrary graphs, proved by Chvatal and Thomassen.