Long cycles in bipartite tournaments (Q1910552)
From MaRDI portal
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