Long cycles in bipartite tournaments (Q1910552): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 06:12, 5 March 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