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 Chvátal and Thomassen.

Mathematics Subject Classification (2010):

• 05C12
• 05C20
• 05C76

Key words:

• Strong orientation
• diameter
• strong product