Abstract
We give a simple proof that everyk-connected bipartite tournament has a cycle through every set ofk vertices. This was conjectured in [4].
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. Bang-Jensen, andC. Thomassen: A polynomial algorithm for the 2-path problem for semicomplete digraphs,SIAM J. Disc. Math 5 (1992), 366–376.
J. A. Bondy, andU. S. R. Murty: Graph Theory with applications, MacMillan Press (1976).
S. Fortune, J. Hopcroft, andJ. Wyllie: The directed subgraph homeomorphism problem,Theoretical Computer Science 10 (1980), 111–121.
R. Häggkvist, andY. Manoussakis: Cycles and paths in bipartite tournaments with spanning configurations,Combinatorica 9 (1989), 33–38.
L. Lovász, andM. D. Plummer:Matching Theory Annals of Discrete Mathematics29, North-Holland (1986).
Y. Manoussakis, andZ. Tuza: Polynomial algorithms for finding cycles and paths in bipartite tournaments,SIAM J. Disc. Math. 3 (1990), 537–543.
C. Thomassen: Highly connected non 2-linked digraphs,Combinatorica 11 (1991), 393–395.
Author information
Authors and Affiliations
Additional information
This research was done while the first author was visiting Laboratoire de Recherche en Informatique, universite Paris-Sud whose hospitality and financial support is gratefully acknowledged
Rights and permissions
About this article
Cite this article
Bang-Jensen, J., Manoussakis, Y. Cycles throughk vertices in bipartite tournaments. Combinatorica 14, 243–246 (1994). https://doi.org/10.1007/BF01215353
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01215353