Identity orientation of complete bipartite graphs (Q1772415): Difference between revisions

An identity orientation of a graph \(G\) is an orientation of some of the edges of \(E(G)\) such that the resulting partially oriented graph has no automorphism other than the identity. \textit{F. Harary} and \textit{M. S. Jacobson} [Discuss. Math., Graph Theory 21, 149--158 (2001; Zbl 1001.05062)] posed the following problem: For which values of \(s,t\) does the complete bipartite graph \(K_{s,t}\) have an identity orientation? In this paper it is shown that \(K_{s,3^{s}-r}\) does not have an identity orientation for any integer \(r\) such that \(3^{r}+1\leq s\) but if \((r+1)(r+2)\geq 2s\) then this complete bipartite graph does have an identity orientation. These results are used to determine exactly the values of \(t\) for which an identity orientation of \(K_{s,t}\) exists for \(2\leq s\leq 17\).