Long cycles in bipartite tournaments (Q1910552): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(94)00273-l / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2090678880 / rank | |||
Normal rank |
Latest revision as of 09:22, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Long cycles in bipartite tournaments |
scientific article |
Statements
Long cycles in bipartite tournaments (English)
0 references
24 March 1996
0 references
Let \(D\) be an oriented complete bipartite graph and \(d^+(u)\) \((d^-(u))\) the outdegree (indegree) of any vertex of \(D\). The digraph \(D\) satisfies condition \(C(n)\) if \(d^+(u)+ d^-(v)\geq n\) whenever \(uv\) is not an arc of \(D\). A \(p\times q\) bipartite tournament \(T\) is an oriented complete bipartite graph with bipartition \((X, Y)\) where \(|X|= p\) and \(|Y|= q\). The main result established is: if \(T\) is a \(p\times q\) strong bipartite tournament satisfying \(C(n)\), then \(T\) contains a cycle of length at least 2 \(\min (n+ 1, p, q)\) unless \(n\) is even and isomorphic to a specified family of graphs.
0 references
loop
0 references
digraph
0 references
bipartite tournament
0 references
cycle
0 references