Pokrovskiy, A;
(2015)
Highly linked tournaments.
Journal of Combinatorial Theory, Series B
, 115
pp. 339-347.
10.1016/j.jctb.2015.05.005.
Preview |
Text
Linking.pdf - Accepted Version Download (197kB) | Preview |
Abstract
A (possibly directed) graph is k-linked if for any two disjoint sets of vertices and there are vertex disjoint paths such that goes from to . A theorem of Bollobás and Thomason says that every 22k-connected (undirected) graph is k-linked. It is desirable to obtain analogues for directed graphs as well. Although Thomassen showed that the Bollobás–Thomason Theorem does not hold for general directed graphs, he proved an analogue of the theorem for tournaments—there is a function such that every strongly -connected tournament is k-linked. The bound on was reduced to by Kühn, Lapinskas, Osthus, and Patel, who also conjectured that a linear bound should hold. We prove this conjecture, by showing that every strongly 452k-connected tournament is k-linked.
| Type: | Article |
|---|---|
| Title: | Highly linked tournaments |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.jctb.2015.05.005 |
| Publisher version: | https://doi.org/10.1016/j.jctb.2015.05.005 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Connectivity of tournaments, Linkedness, Linkage structures |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10112669 |
Archive Staff Only
 |
View Item |
