On optimal orientations of complete tripartite graphs

Abstract

Given a connected and bridgeless graph $G$, let $\mathcal{D}(G)$ be the family of strong orientations of $G$. The orientation number of $G$ is defined to be $\bar{d}(G):=min\{d(D)|D\in \mathcal{D}(G)\}$, where $d(D)$ is the diameter of the digraph $D$. In this paper, we focus on the orientation number of complete tripartite graphs. We prove a conjecture raised by Rajasekaran and Sampathkumar. Specifically, for $q\ge p\ge 3$, if $\bar{d}(K(2,p,q))=2$, then $q\le \left(\genfrac{}{}{0ex}{}{p}{\lfloor p/2\rfloor }\right)$. We also present some sufficient conditions on $p$ and $q$ for $\bar{d}(K(p,p,q))=2$.

16 pages