On Optimal Orientations of Tensor Product of Graphs and Circulant Graphs

Abstract

For a graph \(G\), let \(\mathcal{D}(G)\) be the set of all strong orientations of \(G\). Define the orientation number of \(G\), \(\overrightarrow{d}(G) = \min\{d(D) \mid D \in \mathcal{D}(G)\}\), where \(d(D)\) denotes the diameter of the digraph \(D\). In this paper, it has been shown that \(\overrightarrow{d}(G \times H) = d(G)\), where \(\times\) denotes the tensor product of graphs, \(H\) is a special type of circulant graph, and the diameter, \(d(G)\), of \(G\) is at least \(4\). Some interesting results have been obtained using this result. Further, it is shown that \(d(P_r \times K_s) = d(P_r)\) for suitable \(r\) and \(s\). Moreover, it is proved that \(\overrightarrow{d}(C_r \times K_s) = d(C_r)\) for appropriate \(r\) and \(s\).