Optimal orientations of strong products of paths

  • Tjaša Paj Erker University of Maribor, Slovenia
Keywords: Diameter, strong orientation, strong product

Abstract

Let diammin(G) denote the minimum diameter of a strong orientation of G and let GH denote the strong product of graphs G and H. In this paper we prove that diammin(PmPn) = diam(PmPn) for m, n ≥ 5, m ≠ n, and diammin(PmPn) = diam(PmPn) + 1 for m, n ≥ 5, m = n. We also prove that diammin(GH) ≤ max{diammin(G), diammin(H)} for any connected bridgeless graphs G and H.

Published
2018-08-08
Section
Articles