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\le s$ and $(r,s)\notin \{(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.