Identity orientation of complete bipartite graphs (Q1772415): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 08:50, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Identity orientation of complete bipartite graphs |
scientific article |
Statements
Identity orientation of complete bipartite graphs (English)
0 references
18 April 2005
0 references
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\).
0 references
identity orientation
0 references
complete bigraphs
0 references
automorphisms
0 references