
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\).
Automorphisms, automorphisms, identity orientation, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), Directed graphs (digraphs), tournaments, complete bigraphs, Discrete Mathematics and Combinatorics, Complete bigraphs, Identity orientation, Theoretical Computer Science
Automorphisms, automorphisms, identity orientation, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), Directed graphs (digraphs), tournaments, complete bigraphs, Discrete Mathematics and Combinatorics, Complete bigraphs, Identity orientation, Theoretical Computer Science
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
