Identity orientation of complete bipartite graphs (Q1772415): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2004.07.017 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1983094982 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4350166 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Parallel concepts in graph theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Destroying symmetry by orienting edges: Complete graphs and complete bigraphs / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 09:00, 10 June 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