Optimal Orientations of \(P_3 \times K_5\) and \(C_8 \times K_3\)

Abstract

For a graph \(G\), let \(\mathcal{D}(G)\) be the set of all strong orientations of \(G\). The orientation number of \(G\), denoted by \(\vec{d}(G)\), is defined as \(\min\{d(D) \mid D \in \mathcal{D}(G)\}\), where \(d(D)\) denotes the diameter of the digraph \(D\). In this paper, we prove that \(\vec{d}(P_3 \times K_5) = 4\) and \(\vec{d}(C_8 \times K_3) = 6\), where \(\times\) is the tensor product of graphs.