Optimal orientations of strong products of paths
Tjaša Paj Erker · The Art of Discrete and Applied Mathematics · 2018
Let diammin(G) denote the minimum diameter of a strong orientation of G and let G ⊠ H denote the strong product of graphs G and H. In this paper we prove that diammin(Pm ⊠ Pn) = diam(Pm ⊠ Pn) for m, n ≥ 5, m ≠ n, and diammin(Pm ⊠ Pn) = diam(Pm ⊠ Pn) + 1 for m, n ≥ 5, m = n. We also prove that diammin(G ⊠ H) ≤ max{diammin(G), diammin(H)} for any connected bridgeless graphs G and H.