On Optimal Orientations of Tensor Product of Complete Graphs

Abstract

For a graph \(G\), let \(\mathcal{D}(G)\) be the set of strong orientations of \(G\). Define \(\overrightarrow{d}(G) = \min\{d(D) \mid D \in \mathcal{D}(G)\}\) and \(\rho(G) = \overrightarrow{d}(G) – d(G)\), where \(d(D)\) (resp. \(d(G)\)) denotes the diameter of the digraph \(D\) (resp. graph \(G\)). In this paper, we determine the exact value of \(\rho(K_r \times K_s)\) for \(r \leq s\) and \((r,s) \not\in \{(3,5), (3,6), (4,4)\}\), where \(K_r \times K_s\) denotes the tensor product of \(K_r\) and \(K_s\). Using the results obtained here, a known result on \(\rho(G)\), where \(G\) is a regular complete multipartite graph is deduced as corollary.